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
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.