Tashanna let me know that TeleNav is now supporting the BlackBerry Storm. You can see it showcased on the front of their website now for individuals. I can see the touchscreen being a real asset for the app so this could be really cool. The BoyGenius seems to be really digging it.
They have a 30 day trial at this link. You can see the Storm is now on the supported devices list at this link. A good feature comparison can be found on this matrix just scroll down to the BlackBerry section.