There’s a growing number of tools that analyse Android .apks for app vulnerabilities, over zealous permissions, data leakage and malware. You can find a great list at ashishb.net.
I expect tools such as these and those provided by security consultancies will more important as Android becomes even more popular and pervasive. This takes me back to my Symbian days when I thought that Symbian Platsec was over-zealous and instead, thought a phone might police itself in realtime.
There are probably opportunities for such tools (apps) that go further than just looking for signatures of malware.