Non native 3rd-party apps not loading on Apple Watch
I have just found an unusual solution to this problem: 

Deleting all music from the Settings app on the iPhone and then soft resetting both devices solved the issue.