Welcome to Apple Support Communities! There's an article that includes troubleshooting steps that can resolve your issue. I'll go ahead and paste them below, and while it looks like you've already done some of the steps, there are a few on there you haven't tried yet so I'd give those a shot.
USB printers and Bonjour-enabled network printers
Follow these steps until the issue is addressed:
- Make sure that the printer is powered on, has ink / toner, and that there are no alerts on the printer’s control panel. Note: If you cannot clear an alert on the printer's control panel, stop here and check the printer's documentation or contact the manufacturer for support.
- Ensure the printer is properly connected to a USB port on the Mac or AirPort base station / Time Capsule. If the printer is a network-capable printer, make sure that it is properly connected to your home network.
- Use Software Update to find and install the latest available updates. If an update is installed, see if the issue persists.
- Open the Print & Scan pane or Print & Fax (Snow Leopard) pane in System Preferences.
- Delete the affected printer, then add the printer again.
If the issue persists, try these additional steps: