How's your insulation? Additional attic insulation (walls too and new windows, ideally) may work wonders.

Thanks for the suggestion, but I think my insulation is fine. I base this on:

(1) In the morning (5am), the master bedroom is still warmer than the outside hallway. I'm thinking that that should rule out warm attic + too little insulation.

(2) During the winter, we have to close nearly all of the vents in the master bedroom to prevent it from being too warm.

The house was built in 1984 and has some sort of "energy saver" certification. Based on our first winter here, my impression is that it is well-sealed and insulated (for 1984 vintage). On a side note, all of the ductwork runs within the thermal envelope -- in fact, what air does come out of the upstairs ducts is nice and chilly.

As for air pressure coming out of the floor vents, my hold-my-hand-over-the-vent test tells me that the air is only reaching a height of 4-5 ft or so.

If it was my house I would draw a lay out of the
#1 upstairs ducting #2 downstairs #3 finished basement
This is the layout of how the ducting should be connected.
All you need is a zone control system installed by a licensed hvac company and they will modify the system to save you energy and in turn you will only use in the areas need at that time. This will save you more money than you realize. I have zoned more homes instead of replacing under sized systems due to others replacing systems with the same size of old equipment.

Window units are sometimes a viable option as a supplement to a centralized home cooling system, especially, when used in an upstairs room that the central unit has problems cooling. There are several factors to consider though when deciding if a window unit is right for you. I work for a company in Clearwater, Florida, called ABS Air Conditioning, and we see these types of scenarios all the time here in Florida. I'd be happy to share my expertise with you regarding this topic; if you'd like, feel free to give me a call sometime at 727-608-1251

Actually, we've got a window unit in our basement that we've thought about dragging out of storage and using upstairs until we've solved the problem.

I wonder if it could be leaking ductwork? The reason I ask is that I have both of the basement vents shut (1 is sealed tightly with a magnetic cover), yet when I'm in the kitchen on the 1st floor, I can feel a substantial breeze flowing from under the door at the top of the basement stairs (keep in mind that there is no return duct in the basement). Given the positive air pressure in the basement and the fact that the basement gets pretty cold when the AC is on makes me wonder if the ductwork is leaking, which in turn reduces pressure to the upstairs.

Follow-up: I was fishing some CAT-5 through the basement ceiling, when I noticed that there was a damper in the south branch of the ductwork. Whoever finished the basement 10 years ago built a hallway beneath the damper with no way to access the damper directly. Even worse, the wingnut holding the damper handle in place was slack, so that the handle was hanging straight down (+45° = 100% open, -45° = 0% open, with 0°, or straight down = '50%' open). If I did my sine/cosines correctly, '50%' open really translates 29% of maximum airflow.

I found a pole, pushed the lever to 100% open, and tightened the wingnut by poking at it with the pole (I'm accessing the ductwork by standing on a stool in an unfinished basement closet that allows me to view the gap between the basement ceiling and 1st story floor. The damper was 4 feet away).

The airflow to the upstairs master bedroom has noticeably increased and parts of the downstairs are less stuffy. It was an overcast day in the low 70s today, so it's too early too see if opening the damper completely cured things. Either way, it's hard to believe that the previous owners lived with this for 10 years.