There is no way for any of us to know what settings you may have inadvertantly changed in the service menus. The best indication of
EVDO access is the little "EV" indicator in the upper left corner of the screen. If you are in an
EVDO market, you should see this indicator.
I would not have waited over 2 months to look for answers to this question. Take it back to the Verizon store you bought it from and have their techs look at it. Contrary to popular belief, the best and most effective way to resolve a complex issue like this is the "'traditional' customer service experience". Personally, it sounds to me like something has been turned off on your account, but there is no way to know without looking at your phone.