El principal error es que en una misma página no puede haber elementos con un mismo id (y por otra parte, tampoco los necesitás). Fijate si esto te sirve:
Código PHP:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>test</title>
<script>
function modificar_boxes(v,n){
var inp=document.getElementsByTagName('input');
for(var i=0, l=inp.length;i<l;i++){
if(inp[i].type=='checkbox' && inp[i].name.split('[]')[0]==n)
inp[i].checked=v;
}
}
</script>
</head>
<body>
<form action="" method="get">
<input type="checkbox" name="chk_col[]" value="loquesea" />
<input type="checkbox" name="chk_col[]" value="loquesea" />
<input type="checkbox" name="chk_col[]" value="loquesea" />
<input type="checkbox" name="chk_col[]" value="loquesea" />
<input type="checkbox" name="chk_col[]" value="loquesea" />
<input type="checkbox" name="chk_col[]" value="loquesea" />
<input type="button" name="marcar" value="Marcar todos" onclick="modificar_boxes(1,'chk_col')" />
<input type="button" name="desmarcar" value="Desmarcar todos" onclick="modificar_boxes(0,'chk_col')" />
</form>
</body>
</html>