Over in the Storm forum, this post has some great news.
Garmin is now available for the Storm. Yes, it costs $99 bucks... but it comes with a 30 day free trial. If GMaps fixes their "GUI issue" with the Storm before then, woo hoo... uninstall Garmin, use Gmaps.
Nav4All is still a good free (until 01/01/2010 anyway) app that has a pretty UK Female voice!