I have the same deal. HP 3650 attached to XP, I try printing from FC3 over the network, and doc appears in XP queue.
In my case, the printer initialises but freezes, and I have to manually delete the document from the queue directory in XP (the gui way of deleting won't work).
However, when I connect the 3650 straight to linux it works fine (only tested on FC4 currently), so I'm assuming it's not an issue with the printer.
Any help greatly appreciated.