I've had no luck getting US (or UA or AA for that matter) to open up inventory on other airlines... they've always been willing to rebook me for no fee into any flights with availability, but they have been unable to get partner airlines to release award inventory.
One case, I had an SQ flight in C from SIN-NRT cancelled and was rebooked onto an A380 last year... which was great, except it forced a disconnect with my NH flight home. US was unable to get SQ to open up inventory on other flights that would have worked for me.
Another case, last week I noticed that UA134 was switched from a 3-class 767 into a 757. I had redeemed US miles for an international F award, continuing to MUC, and United simply switched the 3-class SFO-ORD 767 from flight 134 to flight 972 80 minutes later. The later flight still worked for my connection, so I was hoping US could just convince United to put me on it, but no dice. (This is where it helps to have your award ticket booked with the carrier you're flying, as United has gladly opened up inventory for me on flights they've ticketed and operated in the past.) I also called the United 1K line, and the agent I spoke with put a call in to inventory management, but the response I got was that since it was a US ticket, US had to be the one to change it.
So I think you're in a tough situation, unless you can find new availability. I do think you have a pretty good shot at getting US to refund miles into your account, though, even if you have already flown part of your itinerary, since you were involuntarily downgraded... I've had both US and AA do this for me on partner flights where I was downgraded with no no resistance.
Definitely post your experience, regardless... I've been curious if there's some other way to get inventory opened up.