If you are using wireless try plugging into the Express via ethernet, and turn off the wireless in the computer and see if the print can complete.
Interaction between drivers .. eg wireless driver and print drivers are not unknown in the windows world. Ethernet tends to be a lot more stable.
If that doesn't work, have you downloaded the very latest driver for the printer??
Delete the whole setup and install the newest driver again.
My pc is hardwired to the router and the airport express connects wirelessly to the router. My apologies I wasnt clear in my earlier post.
I have the latest printer drivers and have deleted everything numerous times to no avail.
Not sure what the issue is but i think i am about to give up on this!!!