Before you do something rash, there are a few good options. I've liked running "Copilot Live" but with the Galaxy phones getting 2.3, it broke that for us, You'll probably get much better results on the Thunderbolt.
I've been using Navigon (a Garmin company) since it DOES work on my Epic4g. Not too crazy about the interface, but that's a personal preference I suppose. With Navigon, you'll probably get the same quality routing that you are used to from your dead Garmin Nuvi.
I chose both of these because they use locally stored and updated maps, negating the need to even have data running. Makes recalculating much quicker, longer battery life if you don't have the option to plug in while navigating, and you can still take calls without losing the map.