You had said that you had cleaned the tumblers and lubed them. My question is,what did you use to lube them? I always use the "Graphite Lubricant" to lube all my ignition and door locks with. I normally do it once a year, just as a preventative measure. Anything else will just gum up the works in a lock. Try that before going the replacement route.
Oh, you can buy a small tube of the stuff at Autozone, Advance Auto or a similar auto parts store for about $2-3, I think.

Bill Reid
'93 T100 SR5 4X4
'05 4Runner SR5 4x4 (wife's DD)