Just thought I’d throw in my two cents… this could be an issue with Bonjour support within Windows iTunes (?). Does this come bundled, or does it require a separate installation of Bonjour for Windows? (It’s been a while since I’ve installed iTunes on my Windows machine).
Try installing/re-installing Bonjour for Windows (http://www.apple.com/support/downloads/bonjourforwindows103.html) and then verify that you can ping the Bonjour name of the Kubuntu machine from your windows box. If resolution is working, then service discovery should also work. :-