Success!
Ok, I was able to get the HP Color LaserJet 4500N working for color and black and white printing. First, the printer and the computer had to be connected to the same router and not on different routers like the original setup. Second, once that was done, with the latest drivers from HP installed (Jan. 2008), the add printer using AppleTalk showed the printer in the AppleTalk network:) Then, selecting the printer and letting it autoconfigure was all there was too it. Hopefully this will help others.