Okay so I was being dumb!
Turns out you have to do this as well, I had done part 1 but not part 3:
First we'll make sure your user account is a member of the Remote Desktop Users group:
Right click Computer or My Computer and then click Properties.
Click the Remote Settings link or the Remote tab if you are on XP.
Click the Select Users or Select Remote Users button.
If your user name is not listed in there, click Add and enter your user name.
Click Ok and Ok again to dismiss both dialogs.
[*]Once you are done, try reconnecting. If you can connect, stop here - we're done. If you still see the error message continue to step 3.
[*]We're almost done. Next, we'll grant the Remote Desktop Users group the right to log on:
Click Start then click Run. Enter secpol.msc and click Ok.
The Local Security Poloicy window should open up.
Expand the Local Policies node and click User Rights Assignment.
On the right hand side, double click Allow log on through Terminal Services or Allow log on through Remote Desktop Services.
Click Add User or Group and enter Remote Desktop Users.
Click Ok and Ok again to dismiss both dialog boxes.
Restart your PC, wait for a few minutes and try to reconnect using Jump