Just bought this game through the sale on PSN, made sure the game downloaded all the way 100% before attempting to connect online.
I've been checking it every few hours since it finished and no matter what I do I get this error when I start the game.
Hey Wilios, have you tried the steps in this FAQ?