In the end all I needed to do was to clear the caches and restart everything.
- I deleted the ~/.gradle/ directory
- I then restarted AndroidStudio with the "File" > "Invalidate Caches / Restart..." menu item.
After this I started AndroidStudio and loaded the project again, and it worked.
EDIT: Since the update to Android Studio 3.0 this started happening again, and invalidating the caches stopped fixing the issue.
I tried everything I could, but in the end the only thing that worked was uninstalling everything Android-related, and then installing an old version of Android Studio.
EDIT2: I've been using Android Studio 3.1 Canary 5 since it came out, and did not have this problem with it since then. This suggests that the next stable release should have this fixed :/