Ahh, for $6 that wasn't a bad buy at all. That's probably less than it costs Velleman to actually make the things. Methinks RS are doing some stock clearance.
The other thing you could try would be to go into the software settings and turn the speed down as far as it can go. It'll take a lot longer to read, but it might actually be able to do it.
Of course, the other possibility is that code protection is indeed turned on. I've not done ANY PIC work in about a year, and nothing on PIC16 for twice that, but IIRC you should be able to read the config bits regardless of the state of the code protection. This will tell you if code protect has been turned on.
EDIT: Having let my head tick along a little more, I'm now pretty sure that your device has CP enabled. I think what's happening is that the programmer software is attempting to extract the OSCCAL value from the code so that it can be used again, and since the CP is turned on it gets nothing. It's still worth reading the config bits if you can, because I am rusty and by no means an expert, but I'm pretty sure it's locked down.