Uranium-235 has a half life of about 700 million years, Plutonium-239 is about 24,000 years, but it's not the Uranium that's the main problem it's the waste products and poisons that are a byproduct of the reaction that are the worst - things like cobalt-60, caesium-137 etc., they still remain after the fuel has been removed.

After the fuel is removed, the whole of the primary circuit of the reactor is heavily contaminated and has to be dealt with. Usually the whole of the reactor compartment is dealt with as a unit (as it's designed to contain radiation :)). The USA stores them ashore, the UK is as yet undecided on their long term solution and is storing them afloat, with regular maintenance on the hulls to prevent corrosion.

This may be of interest: http://www.armscontrol.ru/subs/disposal/proe1210.htm