Do you have an EU cookie program installed? It may be conflicting with something.
Did you set your cookie directory in Joomla correctly?
Do you have anti-spoofing turned on? (If so, try turning it off to see if that solves the issue)
All of those are suggestions from other threads. Please post if any of those help (or do not help!).