I swear I once had this old Gameboy game that teaches french. Actually, it was more like a, "choose your situation"
[ ] Travel
[ ] Restaurant
[ ] Friends and family meeting
And then it spits out a ton of handy phrases. I once downloaded Talkman for the PSP but the idea of walking up to a stranger, showing my PSP with the "where is the toilet" in a different langauge. Also the fact that I didn't have a microphone didn't help.