I know many of the Android phones have "with Google" printed somewhere on the casing (on my Eris it's on the battery door), and the Android brand has been fairly well associated with the concept of "Google Phone".
AT&T is presumably free to switch the services out as they wish - but I have to wonder if their replacement apps will provide a user experience that is at all tolerable. If things break, don't work as expected, etc. the assumption from the average user is going to be that Google is broken. They don't know or care that AT&T has replaced their services with Bing/Yahoo/etc.
On top of which, users who hear the Android name may expect certain things such as Google Voice, support for GMail, Google Calendar, etc. and be mighty upset when they aren't there.