Hi, I just happen to come across your post here.
Well, your phpinfo() session settings look fine.
When a session cookie can't be created it's usually due to the environment on the (pc) machine you're using. Under the Windows platform, the use of certain software such as Norton Internet Security or Personal Firewall, McAfee Personal Firewall Plus, GhostSurf Pro, and ZoneAlarm may block cookies from being created. Turn these types of software off or adjust their settings to allow cookie generation. Have you tried testing your web site from another computer or different browser at least?
Your error reporting is set to 261. I would set it to E_ALL while testing/debugging this. See:
http://us2.php.net/manual/en/function.error-reporting.php#AEN40763
The other possibility is that you're sending output before the session_start() and you're suppressing or not seeing the warnings. It's hard to say without seeing the code. For all I know you maybe using ob_start() for buffering the output and what I just said may not apply.
You can always provide us with the link so members can test and report back to you. If the DNS is not set on the new site, you should find and post the link using the IP address of the server - i.e. http://111.222.333.444/script.php
That way I can run it and immediately tell you if my browser created a session cookie or not.
.