Make sure the there is not already a local printer with the same name as the printer that you are trying to add, because apparently Windows XP cannot tell the difference. This happened to me and I was greeted with the below dialogue.
There should be the shared printer name under the computer name. So naturally I started to check all kinds of settings on the server, printer and windows client. Luckily I escaped from the wild goose chase. Hopefully this helps someone else do the same.
I was able to set this up in under 2 hours using the Network Printing with Ubuntu and Sharing a printer to Windows XP clients with Samba and Cups guides. The Ubuntu/Linux community has created amazing software and documentation even with something as ugly as printing. If you do not have to play with Windows clients, I highly recommend the CUPS interface.