Why does Fourier analysis of Boolean functions "work"?
Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions $f: \{0,1\}^n\to\mathbb{R}$, and consider a linear operator of the form $\sigma_w$ (for $w\in\{0,1\}^n$), that maps a function $f(x)$ as above to the function $f(x+w)$. In many of the questions of TCS, there is an underlying need to analyze the effects that such operators have on certain functions.

Now, the point is that the Fourier basis is the basis that diagonalizes all those operators at the same time, which makes the analysis of those operators much simpler. More generally, the Fourier basis diagonalizes the convolution operator, which also underlies many of those questions. Thus, Fourier analysis is likely to be effective whenever one needs to analyze those operators.

By the way, Fourier analysis is just a special case of the representation theory of finite groups. This theory considers the more general space of functions $f:G\to \mathbb{C}$ where $G$ is a finite group, and operators of the form $\sigma_h$ (for $h\in G$) that map $f(x)$ to $f(x\cdot h)$, The theory then allows you to find a basis that makes the analysis of such operators easier - even though for general groups you don't get to actually diagonalize the operators.