Why does uncompetitive inhibition decrease the Michaelis constant?
First off, the difference between the types of inhibition:


competitive inhibition: The inhibitor only binds to the substrate-free form of the enzyme. (Not necessarily at the active site!)
uncompetitive inhibition: The inhibitor only binds to the substrate-bound form of the enzyme.
noncompetitive inhibition: The inhibitor binds equally well to both the substrate-bound and substrate-free forms of the enzyme. (Some people feel this is just a non-special special case of mixed inhibition.)
mixed inhibition: The inhibitor binds to both the substrate-free and substrate bound forms of the enzyme. (But not necessarily with the same affinity.)


Secondly, you need to separate out the concept of binding affinity of the substrate from the concept of $K_m$. The binding affinity of the enzyme towards the substrate is just what you think it is: the equilibrium constant between the bound and unbound forms of the enzyme, in the absence of catalysis and inhibitor.

The $K_m$, on the other hand, is an overall parameter of the rate equation, and doesn't necessarily have a direct relation to substrate binding. The confusion between the two arises from the fact that in simple enzymatic systems, under the simplified conditions we normally study them in, $K_m$ is a pretty decent approximation of the substrate binding affinity. Thus you'll have introductory textbooks saying that "$K_m$ is a measure of substrate affinity". -- a gross oversimplification. They're certainly related, but they're not exactly identical - especially when you get to more complex reaction schemes. Confusing the two leads to problems.

The enzyme inhibition cases are an example of this. Enzyme inhibitors (even competitive ones ones) don't change the intrinsic binding affinity of the free enzyme to substrate. Instead, they draw off some of the enzyme from the productive pathway. Because they change the concentration of particular enzyme species, they change the observed rate equation. How they change the rate equation depends on which enzyme species they change the concentration of.

For a full accounting, you really should look at the derivations of the rate equations, and how the extra equilibria of the inhibitor binding changes things. (e.g. here or here) But for something of an intuitive explanation: 

pure noncompetitive inhibition reduces the concentrations of substrate-bound and substrate-free forms equally. (The concentration of product-bound forms being negligible in the standard initial rate equations.) This is basically the same as reducing the total amount of enzyme, i.e. reducing $V_{max}$ or apparent $k_{cat}$.

competitive At saturating substrate concentration, the amount of free enzyme (and thus the effect of inhibition) is negligible. The rate at saturating substrate (i.e. $k_{cat}$) is thus the same. Therefore, it's the apparent $K_m$ that changes. (NOTE! The actual affinity to the substrate isn't changed by the inhibitor. Instead, the inhibitor specifically reduces the amount of free enzyme available, in a way that can be compensated for by higher substrate concentrations. This just so happens to change the rate equation in the same way changing the $K_m$ does.)

uncompetitive At negligible substrate concentrations, the amount of substrate bound enzyme (and the effect of inhibition) is negligible. Thus the rate should be the same with and without the inhibitor. If you recall, the enzymatic reaction rate at negligible substrate is parameterized by $k_{cat}/K_m$. For uncompetitive inhibition, this needs to stay the same. Thus both $k_{cat}$ and $K_m$ need to change in the rate equation, to the same proportion.         

mixed - A mixture of the above effects, depending on the relative affinities to the substrate bound/unbound forms of the enzyme.