Set_cook¡e y session_start se pueden usar juntas sin ningun problema, ahora estas deben de estar ANTES de cualquier salida en HTML, y las cookies solo esta disponibles hasta DESPUES de recargar la pagina, es decir, esto no sirve:
Código PHP:
set_cookie( "mycookie", "algo" );
$valor = $_COOKIES['mycookie'];
Ya que la cookie mycookie solo va a existir hasta despues de recargar la pagina.
Saludos.