SQL Server Replication - Unable to start agent job - Username or Password Incorrect
We have literally just solved this issue. 

It turns out, the SQL agent was configured to run as my user in the following format:

Myuser@domain.com

I simply changed this to use the following format:

MyDomain\Myuser

It suddenly just started working once I changed that.