I've liked how Lost Winds handles it on iOS, but obviously, it was built around the idea of touch screens.
As a gamer, I'm not a fan of digital analog sticks, I've died in games numerous times because of them.
I'd suggest looking at your key mechanics and figuring out a way to make directional movement tap based and other mechanics potentially swipe-based (Your devs will love you :D)
Edit: Also, knowing a bit more about mechanics of the game would get bigger answers on here with more interaction help.
Edit after your additional info: Hrmmm... Diablo/zelda style. Yeah tap-based controls would hamper any sort of combat situation (assuming there's combat... if there's not, tap-based controls are just fine :D).
I'd say your best bet will be an digital analog stick. My advice with that would be to give over the entire left half the screen to the user to use as an analog stick. So, wherever the user puts their thumb down, that's where the analog stick is. There are still annoyances, but nothing is worse than missing the stick and dying, so allowing the stick to "form" wherever the user puts their thumb down is the way I'd go.