Ditto for United. You can use the 500-mile e-upgrades on just about any domestic fare. Similarly, domestically, miles can be used to upgrade just about any fare. (Having said that, there have been a few fares where upgrades are not allowed; but those are few and far between -- I have certainly never run into that problem; even on my cheapies. Examples of "non-upgradeable" fares would be their weekend e-fare specials or deep-deep-discount S-class fares. Although, you can even upgrade those sometimes!)

Internationally, the rules are a little different. Unless you are a 1K (top tier) and receive SWUs (Systemwide Upgrades -- 1Ks receive 6 each year), only fares in class H and above are upgradeable with miles. I would say on average you're looking at a premium of $200-$400 over the lowest available fare to get an H fare. Of course, this varies greatly in some markets and with the time of year. I recently got an H-fare DEN-SFO-TPE roundtrip for $689. In the summer, an H-fare from DEN to CDG was running about $1,200.

If you do fly occasionally to international places, you may do well to look at US' program. I think they give SWUs (albeit a smaller number) to even their mid-tier elites!