I've got the same thing going on with C4380. I also ONLY bought it because it was wireless. I have a Windows Vista desktop machine and a MB. I have to admit that the printer works great with the Vista machine (either wirelessly or USB), but I haven't been able to get my MB to even see it in the wireless mode.
When I first got the printer, after failing to get it to connect, I spent about an hour on the phone with HP tech support before giving up. The first thing the tech pointed out was that the CD/DVD? that came with the printer did NOT support Leopard. If you look at the disk (at least on mine), it clearly says it supports Windows and MAC 10.4.x. So the tech had me delete all references to the printer on my MB. I then downloaded installation software from HP that did support Leopard.
However, after installing the latest version, it still did not connect in the wireless mode with my MB (works fine with a USB hookup). I MAY try the installation instructions in the posting above.
I may have some security issue that is preventing the MB from connecting with the C4380 as I also can't see my Vista computer from my MB.