Django Admin Intermittently Returning 404 On Model Edit
I had this same problem.  The solution for me was to move my calls to admin.site.register() to admin.py.  With DEBUG set to false, your models are lazily loaded, so the registration calls don't always get made.  Apparently admin.py is always loaded at init time, however.
We're using the Django Admin to maintain some data that's exported to a few of our sites. Sometimes when clicking through the standard changelist view to get a model edit form instead of being routed to the correct page we're getting the Django 404 page/template.
It was happening somewhat sporatically, and we could for a while reproduce it by reloading three times:

First F5: 404
Second F5: 404
Third F5: Object change form loads correctly

But lately it's been returning 404 more often than not. It seems to reduce the odds of returning 404 when we bounce apache (gracefully) and gets worse (again, seemingly) with more requests.
Running Django 1.2.1 on Fast-CGI/MySQL 5.1.x
FWIW, I can't reproduce the problem on my VM, but I'm running mod_wsgi there and have Debug=True set in the settings. Otherwise the code and database is identical.