I found the problem, although I have no idea why it caused it. Session handler was set to PHP in global configuration. Changing it to database fixed it. I have it set to that because my database is on a different server, so it can sometimes be a bottleneck. On my development site I had it set to database, so that's why it didn't fail and the live site did.
Thanks for your help, as always it's much appreciated.