I have three Desktops with an nvidia card that haven't had a problem. On Ubuntu DKMS recompiles the nvidia blob loader whenever the kernel is updated.
What operating system are you on? Did you install the proprietary drivers by hand?
Given what you've said, my guess is that you're on the proprietary driver but it isn't being recompiled properly.