What is your distribution?
I am assuming CUPS is running.
What do the logs say?
You could have the wrong driver installed for the printer. The fact you eventually get a completed print job probably indicates the connection is good.
I did have to restart CUPS on a Red Hat system, because it did not like finding a published printer on another system. Given CUPS had to be restarted on an important production system, I unpublished the printers on the offending system, and all is now well.