For me, none of those standar troubleshooting steps worked for me.
This was happening literally on a fresh install, so there are no plug-ins to clear, etc.
I did find a fix though:
For me, the solution posted here, changing the permalinks did the trick! My scenario was exactly as they described, it was an add-on domain.
I hope you get yours working soon, kiraslyeg – maybe this will work for you too!