Well, that explains it.
Fortunately, the same exact memory is still in stock at my local store. And the prices have halved since, so I'm only out 20 bucks.
Also, after 2 years I finally noticed that my RAM was running slower than it could (1066 instead of 1333MHz). Think of all those clock cycles I have wasted!