I had the same problem with my new macbook pro running OSX Mavericks 10.9.1 and a QNAP TS-219P with firmware 4.0.2.
In the end I had to bypass the Time Machine GUI and set the backup volume through the command line using this command:
sudo tmutil setdestination -ap afp://TimeMachine@NAS.local/TMBackup
where NAS.local is the network name of my QNAP. Once that way set the backups worked fine and the GUI responds properly also.
*** the afp:// part of the above command can just be used in the "Connect to Server" menu item from the Finder. I found that the use of the username "TimeMachine" made all the difference, given that I also use the same network server for my normal network shares.