Have you checked Mozilla's cookie manager to make sure your cookie is getting set?
Mozilla -> Tools -> Cookie Manager -> Manage Stored Cookies -> scroll and find your web site's name and then check for all the cookies that are set. Look for PHPSESSID
If its set, then you have a PHP issue some where. If its not set, then there's an issue with how you're generating the session cookie or Mozilla is getting hung up on something.
You might also find "HTTP Live Headers" plugin rather valuable for testing. You can view the HTTP headers as they're being sent from your web server to your browser. You can look for the cookie data in the header and verify if your web server is actually sending the cookie out or not.
I was doing some session work over the weekend and was using Mozilla and I wasn't having any session/cookie problems. I need to check which version I'm on though. I'm thinking it might still be on v1.4. If not, I may have a PC that is still on v1.4 and I can test my code and see if it chokes...