I don’t frequent SF so frequently, but I can see that this question has attracted a fair bit of attention, so let me just summarise my findings here, and hopefully provide something of a solution to those experiencing the same issue:-
It seems that this is a bug with the version of Avahi that ships with Ubuntu Jaunty (http://avahi.org/ticket/284) to do with supplying the UDP payload size, likely as a result in a more reccent change to the mDNS spec (though I haven’t read it myself). As I explained in the comments to the original question, I did try to upgrade my version of Avahi, but my Linux skills are not what they should be and I didn’t manage to get it to work. (Either way, running a 3 year old unsupported OS is really not recommended anyway…)
In the end, I took the plunge, wiped the SD card of the DreamPlug and installed Debian Squeeze on it, which worked fine (albeit only with iOS 5.0+). A discussion of how to change the DreamPlug OS is out of scope of this question, but what it all boils down to at the end of the day is an out of date version of Avahi. Use a newer version and you should be fine!
Good luck!