It has been said time and again, from RIM reps and from Verizon reps, that the handheld has EV-DO capabilities built-in but not supported by firmware/OS yet. This will come within a few months. If they told you that it would not work, they are correct in stating that... Currently, it will not work. In a few more months after their next OS release that does support EV-DO, I'm sure you can call back and they will say that it does support it.
A more appropriate question would be to RIM asking if the EV-DO chip was built-in to the 7250.
In the beginning the Universe was created. This has made a lot of people very angry and is widely regarded as a bad move.