Whenever anyone runs into problems with flash and cookies, I immediately think of this long running flash bug.
You should be able to verify whether it is this one by printing out the session id server-side (when you receive the upload request) and comparing it against the session id in the browser (using firebug or equivalent). If it is different, I think it is safe to say it is this bug's fault.
The usual way to work around it is to append a GET variable with the session to the upload url, then take that and manually set it to be the session on the server-side.
Here's another SO thread about this problem that has a good answer (unfortunately not specific to php, but might give you a good idea).
Also, I have seen a fair amount of php solutions on google (flash + upload + cookie), but haven't solved this problem in php specifically so I can't recommend one source over any other.
If you have the time please sign up to adobe's bug tracker just to vote up the bug so we can make it really clear to Adobe that it is affecting a lot of people.
Hopefully that's enough detail to get you off to a good start.