Is netatalk on Linux unreliable for hosting Time Machine volumes?
My experience is netatalk is fine until the volume is full and Time Machine starts removing old backups selectively. The deletion process (which involves unlinking a whole load of hard links) seems to be the point at which netatalk falls over and you get the dreaded 'verification' message.

From what I can tell, people who say "it works fine" generally haven't got to the point where their disk is full. 

However even external hard drives connected to a AirportExtreme are not immune to this error message. The only completely reliable backup systems I have used are the internal hard drive in an AirportExtreme, and a USB hard drive connected locally.