Is this a wifi printer or are you saying it's plugged into USB on the AE? If it's USB, check the Airport Utility printer settings to make sure it's being seen by the base station.
Another thing I've seen is that for some reason, the printer gets "paused". Open up the printer queue and make sure it's not paused.
Steve