We were having a similar issue with a production site, and thought it was NextGen Gallery causing the problem (since that is where we most noticed the issue).
Permalinks would break every time while:
Editing a Post or Page
Viewing a Post or Page in Admin mode
Viewing (or changing) any settings for NextGen Gallery
Viewing (or changing) any settings for HeadSpace2 (must activate ajax).
Turned off all plugins, then turned on NextGen Gallery and Custom Post Type UI, testing "known break" actions between each. Custom Post Type UI caused the issue to start again.
I compared the previous versions (back through 0.4.1) and found that
flush_rewrite_rules(); had been removed at 139 (v.0.5.2). Adding that back in prevented permalinks from breaking.
Turned the remaining plugins back on and re-tested, fix still seemed good. Haven't put it on the live site, awaiting input.
Sorry I can't provide a patch at the moment.