I just recompiled the kernel to add some unrelated drivers. After recompliling the kernel I needed to reinstall the NVidia kernel driver. I had already tried reinstalling the kernel driver, but that didn't help.
Today I accidentally reinstalled the NVidia GLX kernel as well as the kernel driver, and now FSAA has started working!
Unfortunately I have no idea how to recreate the problem :-/
anyway, here's a screenshot of 4x antialiased tux racer to celebrate