I have done some additional research on the HP/Microsoft site. The printer is not certified for use with Windows 2008 R2. This usually means that it may work or may not(I was successful with the LasertJet 3050, the Laserjet M1319f MFP would not work).
I have come to the conclusion that the printer is not supported with Easy Print. I could not get the HP universal driver to work with the printer either.
This question can be closed. I will move the affected users over to my Windows 2003 TS server.