Try switching it to all_party_privilege_map. Typically this has helped a lot and I've been wiping out acs_party_privilege_map usage as I find time to do so.
This view's usually fast in Oracle, too.
It also uses a union but it doesn't explode exponentially the way the union in acs_party_privilege_map does.
Anyway ... I'd appreciate it if you'd give it a try and let us know if it speeds things up or not. If so, I'd more than welcome a patch submission to the SDM to both fix the bugs you've pointed out plus the speed fix, and will put it into the 4.5 tree.
If this doesn't speed things up significantly I'll think harder :)
