I'm not sure why they would want your IMEI number - except maybe for their records.
It has been my experience (based on 2 phones... which is not a lot, so your mileage may vary), that 3G phones require 3G SIMs. 3G SIMs are downward compatible and thus work fine on older phones, but older SIMs don't work on 3G phones very well (a lot of features are disabled and things like voicemail don't work well). For AT&T, a 3G SIM has a little fireball on it with "3G" written on it.
But with AT&T, with the sole exception of the iPhone, you should be able to take any "3G" SIM, pre-paid or not, and put it into any other AT&T compatible SIM-based GSM phone and have it work fine. And, you should be able to take any SIM from AT&T and put it in any non-3G AT&T-compatible GSM phone and have it work fine. iPhones require AT&T activation (or, hacking) so they are the only exception that I know of.