I found an error in our user database and I think I have it fixed now. I also had to mass delete some private messages of people who had around 100 messages stored. I also tweaked the database a little to reduce its size and this might help to speed things up.
If you have any problems, post them here please.