Hi Sam,
Confirm that you have given the Service Account adequate permissions to your Active Directory.
In instances like this its best to delete your User Profile Service application and rebuild it again. I highly recommend you refer to Steve Harbar's article. It was built for SharePoint 2010 but works just as well for 2013.
http://www.harbar.net/articles/sp2010ups.aspx
Hope this helps.
Daniel Christian (MCTS)