This seems to be a problem with many users. I see it all over the net (avahi forums, here, Debian forums, etc...).
The odd part is that nobody ever seems to respond when people post questions. This holds true even on the avahi forums!
This message is a useless message as it does not give you an IP address of the host that sent the original query and basically gives you no way to track down what the problem is.
To make matters worse even the developers are not responding when asked how to get rid of the messages in your log files.
In my own Fedora 12 install and some of my co-works running Fedora 12 we get 3 lines every 3 to 5 minutes! My logs are full of these garbage messages.
Best bet is to go to the avahi community page and select the bug tracking, IRC, Mail lists, etc... to follow this issue. I have added links below:
Avahi Community page:
Seems like the bug tracker at avahi.org has some idea of what is happening. Take a look at this bug:
Not sure if this applies to you but it mentions Mac OSX (Snow Leopard) on the network as a culprit of the message. In our network we do have some Mac's running Snow Leopard so it seems to apply for us.