From what you describe, this is a shared printer, not a a true network printer, which may be part of the problem on a Windows printer share. Are you using generic drivers on your MBP or the specific drivers for the HP Deskjet 810C? If you haven't loaded the right drivers onto your Mac, do so either from the printer install disk or by downloading them from the HP website. Then, add the printer again, and the correct drivers should auto-select.
I've had mixed success with shared printers in mixed-platform networking environments. Some work fine, others just won't. The best solution I've found in recent months is the HP Deskjet 6940 printer, which is a true network printer and hops onto your network by hooking it up to your router via its ethernet interface and performs brilliantly on both Windoze and Mac machines. They cost about £80 here in the UK but I am sure they are much less in the US -- just about everything else is....!