Problema con session_start

[paxarin]

Muy buenas.
Tengo un problema con la hoja verificar.php.
Me aparecen los siguientes errores:
Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /homepages/21/d413773639/htdocs/php/verificar.php:1) in /homepages/21/d413773639/htdocs/php/verificar.php on line 2

Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /homepages/21/d413773639/htdocs/php/verificar.php:1) in /homepages/21/d413773639/htdocs/php/verificar.php on line 2

Warning: Cannot modify header information - headers already sent by (output started at /homepages/21/d413773639/htdocs/php/verificar.php:1) in /homepages/21/d413773639/htdocs/php/verificar.php on line 19

Por extraño que parezca en el servidor local funciona sin ningun problema pero al subirlo al servidor no pasa de aqui.
Revise información sobre este tipo de errores y todos me comentan lo mismo....espacios, saltos de carro, etc. Pero sigue la cosa igual
Aqui os dejo el codigo de verificar.php

Código:

<?php
//Verificamos que las variables contengan datos
if (isset($_POST["usuario"],$_POST["clave"])){
    //conexion con el servidor
    include("conexion.php");
    
    //Limpiar datos para evitar SQL Inyection
    $usuario=mysql_real_escape_string($_POST["usuario"]);
    $clave=mysql_real_escape_string($_POST["clave"]);
    //encriptar la contraseña
  	$salt = 'aca pone lo que quieras';
  	$encPass = md5($clave.md5($salt));
  	
    //consultamos la información
    $rst_usuarios=mysql_query("SELECT * FROM usuarios WHERE urslogin='".$usuario."' AND usrclave='".$clave."'", $conexion);

    //Contamos cantidad de resultados
    $num_registros=mysql_num_rows($rst_usuarios);
    
    if($num_registros>0){
		$fila=mysql_fetch_array($rst_usuarios);
		setcookie("usuario_nombre",$fila["urlogin"]);
		session_start();
		$_SESSION["usuario"]=$fila["usrclave"];
        //mostrar pagina del menu
        header("location:menu.php");}
        else{echo "El usuario o la contrase&ntilde;a no es valido";}
    mysql_close($conexion);

}
?>

Tambien probe a poner session_start() al comienzo del php pero nada.
LLevo más de 3 dias con este problema y no termino de avanzar.
Por favor alguien puede echarme una mano con esto?

[kiko's]

¿Probaste a eliminar el carácter BOM? http://es.wikipedia.org/wiki/Marca_d...ytes_%28BOM%29

Muchas veces ese es el problema.