I just unlocked Deidara and Sasori so I will tell you how to do it. To unlock Deidara and Sasori, you have to clear Shino's request in the story mode. In the Chapter Four, when you get out Godaime's office, instead of clearing the "normal" mission, go down of the town ( there are two red circles, one above Tsunade's office and another one at the bottom of the map ). Once u're there, you'll see again two red circles : one is near the river, that's Shino and the other refers to Temari. By clearing Temari's request (easy to understand), u'll unlock Kisame and Itachi. Shino's request : He'll give you 6 sort of bags to catch butterflies. Leave Konoha (huge gate), u'll be in a forest where the enemies are all butterflies. BUT there are two kind of butterflies : weaker ones (very easy to kill) and more powerful ones (resist more to ur attacks). Catch a POWERFUL butterfly by pressing the button A (the char will throw the bag instead of his special). i advise you first to damage him a little, when little hps left just throw the bag. Use all ur bags and Naruto will automatically leaves the forest. I've caught 3 powerful butterflies, that was enough to unlock Deidara and Sasori. Go back to Shino, a japanese message will confirm u the unlocking characters.
Hope I was enough clear in my message Have a good game =D