This thread sent me on a search of the registered trademarks database (here) where I found a variety of fascinating dead and abandoned UA trademarks:

Lame, fortunately no longer used:
UP THE HILL, DOWN THE HILL: (ABANDONED) IC 039. US 100 105. G & S: early check-in, transportation and storage of baggage and ski equipment of airplane passengers
Filing Date: June 23, 2000
Abandoned: April 30, 2002

OFFICIAL AIRLINE OF THE MILLENNIUM: (ABANDONED) IC 039. US 100 105. G & S: transportation of persons, property and mail by air
Filing Date: March 25, 1998
Abandoned: March 27, 2003

It's been around longer than I thought:
WILMA: (ABANDONED) IC 039. US 100 105. G & S: airline passenger boarding. FIRST USE: 19941001. FIRST USE IN COMMERCE: 19941001
Filing Date: October 21, 1994
Abandoned: September 28, 1995

Discarded additional elite levels:
PREMIER DIAMOND: (ABANDONED) IC 039. US 100 105. G & S: bonus program for frequent travelers, namely, priority boarding, check-in, seating and reservation services; ticket upgrades; augmented frequent flier mileage and passenger air transportation
Filing Date: September 30,1997
Abandoned: April 14, 2000

PREMIER ELITE: (ABANDONED) IC 039. US 100 105. G & S: bonus program for frequent travelers, namely, priority boarding, check-in, seating and reservation services; ticket upgrades; augmented frequent flier mileage; and passenger air transportation
Filing Date: September 30,1997
Abandoned April 21, 2001

An idea for a LCC, a la TED (RAR!), quickly squashed:
AIRWISE, AIRWISE BY UNITED, BASIC BLUE, BASIC BLUE BY UNITED, U II, and U II BY UNITED were all filed on June 20, 1994 and abandoned on October 24, 1994. (Discuss: Do those names sound sufficiently cheap and classless? Do they make the point of association with United? Are they better or worse as a name than "TED?" RAR! TED does not feel threatened!)

And my personal favorite category, the hilarious:
TEDARITA: (ABANDONED) IC 033. US 047 049. G & S: alcoholic beverage, namely premixed cocktail
Filing Date: January 30, 2004
Abandoned April 27, 2005