Fixed it by going to Android Studio -> Preferences -> Gradle -> and ticking Offline work. Still have no idea what was wrong, but at least now it compiles.
Edit:
In new Android Studio Versions the path is File -> Other Settings -> Default Settings -> Build-Excecution-Deployment -> Gradle