I'm finding your post a bit hard to understand.

What do they tell you when you call? Do you mean that there is NC availability, but they don't clear you automatically? I have never had this problem, but it is the topic of this thread.

Yes, this is completely standard. Unless united.com or KVS is showing false availability (which happens from time to time), you should clear immediately.

Right, but this is clearly an error, and, in most people's experience, a rarity.

Just to clarify, the upgrades on the DM list are sorted by status, then fare paid, then the order you are added to the DM list (checkin time). The order of upgrade application does not come into play, according to FT conventional wisdom.

Just to let people know what happened here in the end. I was on the PA waitlist as far as the agents could see but something must have gone a bit wrong in the system. Got a very helpful agent next time I called, who had to redo the whole LHR-SFO-HNL upgrade (but not the return) to make it stick. Still not clear what was wrong, agent went away for a few minutes to be replaced by the cheesy United music, and when she came back just told me this, and said she'd been able to upgrade both legs this time. So http://www.flyertalk.com/thumbsup.gif to the agent. She did say what the first agent told me as well, that things like this happen sometimes. It certainly wasn't a completely new problem to her. Only other thing I can think of was that the SFO-HNL flight had a schedule change a few weeks ago and my waitlist disappeared for both SFO-HNL and HNL-LAX from .bomb though an agent said they could still see it and made sure it was on the PA list then. The HNL-LAX leg cleared normally without any further intervention after that though so not sure what happened.