Just thought I'd add that we DID request an upgrade online (DEN-OAK so less than 1000 miles) and selected 2 500 mile PAPER upgrade certs as payment type.

It worked just fine.

The gate agent smiled and said, "yay, this works! Usually I have to hand these certificates back to people and say sorry"...