My friend had that happen just before Christmas. He was flying with his brother on the same PNR, had purchased the ticket on UA.com, applied for an upgrade for both of them using 500's, upgrades confirmed at his 2P window, all done online, all looking OK.

When he went to OLCI, he was shown his own check-in no prob, but his brother's line on the itin was x'd out and had the 'unable to locate' message. He called UA, waited on hold for 30min to be told: "uhhh, ummm, go to airport early?". They had a 7am flight on Fri 12/21, so 'going early' was not really a viable option.

I called UA web support on his behalf, the agent couldn't figure out why this happened but agreed to try to fix it, put me on hold for 10 minutes, solved the problem, and I was able to complete OLCI on my friends' behalf.