Your issue seems unrelated to the absence of natural key methods. I tested your [original] code as-is on Django 1.4 and 1.2.5 using SQLite and was able to dump data with natural keys with no errors.
After some searching, I found that this issue appears when there are cyclic dependencies between models (including models with self-references). As your updated code shows, there's a self reference in the Users
model, so that's where the problem is. This bug was introduced in Django 1.3 and, despite being already fixed, it's still not available AFAIK in the stable versions (tested up to 1.4.3). In the beta version (1.5b2), however, your code works fine.
If using a beta version (or downgrading to 1.2) is not an option, then your only solution might be creating another model indeed. Something like:
class CreatedBy(models.Model):
creator = models.ForeignKey(Users, related_name="created_by_user")
created = models.ForeignKey(Users, unique=True, related_name="created_by")