If you're getting this message, while trying to play a game that until 'now' worked on your card just fine. Then formatting may help.
Usually the message occurs the first time you try to play a game, and it occurs because you have the incorrect savetype (set via xmenu). It can also occur if you accidentally change the savetype for a particular game.
You can fix the usual occurance by either manually trying the other save types till you find the right one (highlight the game in xmenu, hold select and press left or right on the d-pad to cycle through savetype options), or get a newer version of the savetype database which is usually available wherever you get your firmware from.