There are many humorous reasons but if your looking for why the Bush administration probably really didn't engage in this sort of negotiation (there were opportunities) is that it was their policy to NOT engage in negotiations. Once labeled part of the "axis of evil" there would be no "honorable" way to deal with the matter except to use force.
Due to Clinton's "bumbling" there are two people freed from false imprisonment and "worse yet" we may even be able to come to some sort of arms agreement with the country in the future.
(I think it's time we got a "rolly-eyes" and a "tongue-in-cheek" smilie)