Seriously considering bad unit (less likely) or bad network (more likely) as my issue.
Give Apple support a call and explain your issues; they may swap it out for a new one. I STILL have the affected ATV3 that needs a restart every time to connect! Being in the UK, they kept the replacement programme very quiet.