Paul; did you ever set up the Cookie settings in the ACP, I know they're not compulsary, but it's just an idea as I know of a couple of people who have set this information up, it working for a couple of months and then suddenly stopping, this was resolved by removing all the information from the cookie settings.
I didn't bother putting any information in the cookie setting on my board and people still stay logged in, so I'm not 100% sure what the idea of the cookie settings are.