Problems accessing movies on MacBook Pro via Apple TV
I had the exact same problem as this before. Any number restarts and reboots in any order did not solve the problem.

At the same time I had a DNS issue with the default router setup from my ISP. When I changed my routers DNS to use the Google DNS it also solved my iTunes sharing problems. 

I don't know if this is actually what caused it or if it was just a big coincidence but it's been working fine ever since.