What php version? is it a linux or windows server?
You may need to add session_commit() before the redirect in some cases I seem to recall this from earlier versions of php on linux servers... you might want to give it a try and see if that fixes it.