I believe i figured this on out...just some info for others in case they run into this:
-They were previously on an old BES that was hosted by us. We got them their own BES server.
-Unless you have the Blackberry Java Developers kit (I think), you have to wipe the handheld and perform EA completely after it has been wiped. The IT Policy is not completely removed from the phone if you just delete the user and have them hard boot.