"I'm using the latest nvidia driver available in the repos (the one for Geforece 6 and later). Is there another way to upgrade?"
i'm not sure that the latest driver is the right one for this older video card, i hope i'm wrong but you could need a older version
when you download a driver from nvidia it is not necessary to compile it but it can give you problems that this version of driver doesn't have
"How would I upgrade the kernel? According to synaptic package manager I'm fully updated...."
the kernel is not updated by synaptic, you have to search the newest one in synaptic and install it
sometimes a new kernel is harmful for some people so this is a security measure
all you have to do is open synaptic and press search button, write kernel and press enter, the list of results will have many, scroll down to see kernel 126.96.36.199, your cpu should work well with bfs or normal kernel
this won't remove the older kernel but will add a new option to your boot menu, the new kernel will be listed, select it and let it load for the first time, it can take up to 5 minutes, but only the first time
compare results with older and newer kernel to see if does something for you
do you have to run at this very high resolutions?
sometimes is helpful to use compiz on this situation, it forces the video card to work more and leaves cpu with less load