Ok, this was solved by using a combination of the replies from @mediagirl and @andiefairlie, neither were quite there but they led me to the solution.
NOTE: I didn't state in the question that I am using https://github.com/focuslabllc/ee-master-config for this set up.
The issue was that the login was setting the cookies' domain to the original site (a production site that has been cloned), so .original-site.com
On local this didn't cause an issue as the site was set at local.original-site.com
and the domain was correct. In contrast when it is on the dev server it is original-site.my-dev-server.com
and the cookie domain is now an issue.
To resolve this I added the following to the config/config.dev.php
$env_config['cookie_domain'] = 'my-dev-server.com';
and all was well.
I am unsure if this tied to EE v2.1.3 or a weirdness in this particular install, as I do not run into this on later versions. (I am not the original dev) Your mileage may vary of course.