The HP CLJ 3500N is the one with the built in network the standard 3500 is USB which is what we use.
Now, a couple of things to check first.
Have a look at the CD with the printer and find out where the .inf file is - you need that information when asked to install the driver.
Make sure the printer is plugged in to the USB port of the NAS and is switched on.
You may have to uninstall the printer driver on your PC but I an not sure of this.
The procedure to install the printer as a network printer.
1) open Control Panel and select Devices and Printers
2) select Add Printer
3) select Add Network Printer
4) it should search for printers and when it finds' lp on DLINK-xxxxxx' you can stop the search (the xxxxxx is from the NAS defaults)
5) highlight the 'lp on DLINK-xxxxxx' and click next
6) on our test machine it cam up with no driver found and opened a select driver dialogue (if you still have the driver installed it will maybe find it)
7) assuming no driver found select have disk in the dialogue box, click next and select the cd and folder where the .inf file is, click next.

the driver is installed and you are invited to print a test page, do so and then click finish.
9) you should now have the printer appearing in the Devices and Printers panel.
NOTE: The test page will give you the information on such things as printer name, port name and so on. These are what you need to use when selecting the printer in the print dialogue of various programs.
The above worked for us with the HP laser and a couple of inkjet printers (a Brother and a Lexmark). The brother does pop up a notice saying the print job has been sent to the printer but other than that we were unable to find any odd jobs left in the print spool folder.