On my laptop, connect to the SharePoint 2010 server which is across the internet, no VPN. I can edit workflows, save them, but not publish.
I did have to edit reg keys per this article to get the designer to work: http://support.microsoft.com/kb/2123563
Edit: Looks like the issue is that I need to log in from the server itself, and use the machine name in the URL, not the external machine name. So we have a general issue in that outside people access the machine as http://foo.bar.com, while any admin functionality must be done using http://localname/
I suspect that this server is not really set up correctly, or needs to be aware that it has two names.