As an FYI, some Palm Pre users had a similar issue where the Sprint Nav reverted to a "lesser" state a couple months after activation. I saw the threads about this on PreCentral but didn't follow them since I wasn't having the same issue.
I guess what I'm trying to say is that this may not be EVO/Android specific.
Well, yesterday it was fine after I entered the application when I returned to my home Sprint location. No Lite or Premium designation, just Sprint Navigation. The difference seems to be the Service Plan Code (under Diagnostic Tools in Sharing and More). I will check out the SprintUser thread referenced above.