None of the things mentioned earlier here did actually work for me. But then I found this menu entry in the file menu Invalidate Caches/Restart which appears to have fixed the problem.
I don’t really know what happened in the background but when Android Studio started up again the status bar said Indexing... for a minute or so which apparently did wonders.
For reference I’m using Android Studio 0.5.4.