Are you just a hot-head?, because I really don't see why you should be so pissed off.

1) You clearly didn't do your homework on the upgrade, CO.com makes it clear that non-elite members need to purchase Y, H, K, N, or B fares to upgrade. You may be in luck, they will usually let you buy-up to a higher fare class without charging a change fee, and if you're lucky they may even let you change your flight to one where upgrade rewards are available. It's happened to me.
2) While the agent probably confused you by stating that First Class was "sold out" on your flights, when (s)he meant to say FC upgrades were unavailable, you have to remember that this is a frequent flyer reward you are looking for, and they are always capacity controlled. If you called asking for a free coach ticket for 25,000 miles, there's a good chance you would have also been told it was "sold out" too (This is CO we're talking about). You would be entitled to be upset or annoyed, but probably not "so pissed off"
3) Keep in mind that there are a lot of business travelers on NY-LA flights, many of whom are allowed by company policy to purchase First/Business tickets, and with the discounted FC tickets being available for ~$1K, they actually sell a lot of premium seats on this route. Plus demand for advanced mileage upgrade rewards is high as it's such a long flight, so any seats that may have been allocated for reward upgrades were probably taken already.

I think you probably just had unrealistic expectations as to how easy it would be to get in the front cabin without paying for it with cash. Temper them a little, try for an exit row (which you may or may not be able to get as a non-elite), and follow the advice posted here. Namely, call CO and find out if any other flights have upgrade availability and see if they'll let you purchase the higher fare and change your flight for no extra charge.