I tried this excellent application with the same error message
By trying different CD's from various artists I found the following:
All the original CD's I used managed to get a reply from the freedb website
Copies often worked, but not always
I suspect that what has been said by others on their replies that the error message is misleading, is true
I have tried another application which also accesses freedb, that didn't always work
In fact Windows Media Player doesn't always work either
I would be interested to know what others have found when using original CD's and copies