Clear uses an even higher frequency spectrum than T-Mobile's HSPA+ or EDGE network. T-Mobile's EDGE network is at 1900MHz, their HSPA+ network at 1700/2100MHz, and Clear's network is at 2500-2700MHz. The higher the frequency, generally the weaker it is for building penetration. When you're downstairs, that signal has to go through a lot of walls, possibly also in surrounding houses, as well. This is especially true if Clear's antennas are far or aren't very high up (and if your location is like mine, Clear keeps their antennas usually below other cell networks' in shared towers). In comparison, AT&T's and Verizon's networks usually use 850MHz (sometimes 1900MHz), that's why they have more coverage...fewer towers needed to cover bigger areas. Verizon's upcoming LTE network will be using 700MHz. That doesn't mean you can't build a solid network with high frequency spectrum; both T-Mobile and Sprint have build solid networks in a lot of big cities, but you can't expect Clear to do that immediately... takes time. From their coverage maps, most of their new launch cities' coverage look like Swiss cheese.
Another factor is the hardware's antenna(s), which is very important for weaker signals. From using so many devices on T-Mobile's HSPA+ network, I've noticed some phones (from my use, Sony Ericsson and Nokia) get very good 3G signal, while others (like my previous HTC Nexus One or Samsung) was atrocious and lost 3G all the time. The same thing you mentioned happens in my two story home with weaker phones... parts of downstairs I get 1 or 0 bars (2 at best), while upstairs I get full signal. Those with stronger reception get me solid coverage everywhere in the house (2 signals minimum) although it does improve upstairs.
Current: Motorola Atrix HD with AWS 4G and LTE.
Past providers: Page Plus, AT&T, T-Mobile, Virgin
Past phones: HTC One V, iPhone 4, Nokia Lumia 900, Nokia N9, Samsung Focus, Samsung Captivate, iPhone 3GS, Nokia E61i...