So neither of the Shift keys work? There is a right, left and a shift lock. Shift lock works, though, right? Turn it of, and unplug it. Either blow out the keyboard with canned air, or vacuum it out with a brush attachment on the vacuum. If that doesn't fix it, you may have to opt for USB keyboard if it is too annoying!
Post back with results!