When you say that there are "seats available", how do you know?

If you are just looking at the seat map, that's essentially meaningless. There may people with reservations who don't yet have seat assignments. This is particularly common when booking through another airline or a travel agent -- you often have to go to the operating carrier's site to select seats and many people just don't bother. But they still have a ticket and UA has to hold an empty seat for them, to be assigned at check-in or at the gate.

So you might see empty PP seats on the seat map even if PP is sold out. This would explain why several agents have told you that it's full.