I think the best bet here is to create a formula field on your Account Object that holds the text of your ME1__r.FirstName field, which of course will track the changes in the ME1__r relationship, then when you need to fire your workflow off, use PRIORVALUE on the formula field.
So the new formula field (called Current_Name__c) on Account will hold:
ME1__r.FirstName
And then your workflow rule field update (to what I called Prior_Name__c) will set your target field to:
PRIORVALUE(Current_Name__c)
I have just whipped this out on a developer edition and it does what I believe you are after nicely.. So when I change the ME1__r field on my Account, the formula field (which can be hidden everywhere from sight) reflects the CURRENT name of the relationship, and Prior_Name__c (your target field) holds whatever the firstname of the user was before I made the change.
Is this any good for you? If you are out of fields/adverse to this solution, I think you will probably have to set sail on the Trigger ship :)