Wow, ask and you shall get it... Thanks!

It already exists:
http://www.midomi.com/
except you have to sing or hum the tune

You'll probably never be able to whistle a tune and get an accurate match consistently, but if you can record the actual audio, mobile software for identifying music has been around for a few years.

This may sound dumb, but one thing along these lines that I've wished for for a while now is a tune search... ie, you have that tune stuck in your head, but no idea what it is. If you can do voice recognition, could you do tune recognition, ie, whistle the melody into your phone, and get a list of potential matches from Last.FM or something?

I personally am annoyed whenever people stick a new, trendy name to old-hat ideas. Your phone is too slow do do some things on it's own, so you have your phone act as a lightweight workstation while a server/servers handle the heavy lifting. But now we call it 'cloud computing'.

The 'real' reason why they call it cloud computing: because most people don't really know what it means, but it has a neat name and allows people to imagine that it's something really cool. Sort of like when you catch a quick glimpse of a cute girl but don't get a good look, and then you look at her more closely and realize she's a dog.