I've had the exact same problem since I bought the game.
Pretty disappointed too, the amount of time spent waiting to get a game is longer then actually playing a single game. Almost seems like a waste of money in my opinion
Ok, seriously what the **bleep** is the issue with the cross play between the two systems? I can't exactly explain it but I got both versions and for some reason the PS3 version couldn't join invites or any online game. Tried it on the Vita and it worked wonders, so when I tried going online again with the PS3 version and got knocked out. I tried inviting my friends again on the Vita version and then that one got locked out and all of a sudden the PS3 version started working again all of a sudden....somewhat.
Another thing I noticed: the more times it goes through the Searching/Connecting cycle, the more likely your character will be different than the one you actually chose once you finally get a match started. Typically, I will wait until it says "Connecting..." then just start mashing the Circle button, so if it drops back to "Searching...", it goes right back to the character select menu and I can try again.