North American-market 3G phones seem to always support both UMTS 850 and 1900. I guess it's the same issue we saw with tri-band 2G phones... they tended to support 900/1800/1900 or 850/1800/1900. With some providers that would be okay, with others it would be far from optimal.
Really, though, you have no choice here. Either you get a new phone, or you live with what AT&T gives you.
We have similar issues here in Canada. I am not certain exactly what frequencies are universally used (if any) for 3G - in dense urban areas it's certainly both 850 and 1900 as all the major carriers have spectrum in both frequency ranges - but we have the identical issue with 2G EDGE here. In the city where I live, it's at both 850 and 1900 MHz so my European tri-band 900/1800/1900 EDGE-supporting phone works perfectly, but at my cottage, EDGE is at 850 MHz and 1900 MHz is GPRS only. I get voice service, but very slow data service.
You can pick up a phone like a Nokia E63 pretty cheaply unlocked (that's my unlocked 3G phone until my ordered-this-morning iPhone 4 comes). That will give you the good 3G service here (granted, that particular phone is UMTS, not HSPA) and has quad-band 2G so you can use it in a pinch at home.
CA: SaskTel, Wind postpaid; Rogers, Bell postpaid iPad flex plans; US: T-Mobile postpaid data, prepaid voice; PureTalk (AT&T MVNO) prepaid voice/data; AT&T prepaid iPad plan
Hardware: Too much but notably iPhone 5, iPad Mini Retina LTE, Moto G LTE (N.A. version), iPhone 4. All unlocked.