When you say
It often doesn't print using the USB connection.
do you mean it sometimes prints? That smells like hardware. At the least, it is wise to rule out hardware before beating yourself over the head with software for hours and hours.
The first thing I would do would be trying a different USB port on the computer; then removing the USB cable from the printer and reseating it (trying a different port on the computer did this already at that end); making sure the connectors are clean, then trying a different, tested USB cable; doing one step at a time, testing after each step, in that order.
While testing, I would also try sending print jobs via the lp command (this may require setting the printer as the default, which can be done via the Gnome control center, at least in Debian) and capturing the output for both successful and failed print jobs.