People first thought there was a back door because they wouldn't release enough info on the algorithm to give people a chance to see if they trusted it or not.
not the algorithm, which was public from the start, but the rationale behind the selection of its parameters.
After it was all common knowledge, people examined it and came to the conclusion that it was secure,
the rationale remains classified; some people question nsa's motivation in keeping that aspect of des secret. i believe nsa keeps it secret to avoid teaching potential (or imaginary) adversaries advanced cryptographic techniques. (and also because keeping secrets is what nsa is all about. they seem to be very, very good at it.)
though questions are still around about why it was changed from 64 bit to 56 bit,
you mean 112 -> 56. this has been resolved -- it seems that longer keys don't impose any additional complexity on des attacks. although these attacks were discovered by the open crypto community only a few years ago, nsa had these techniques in hand long before. the bottom line is that additional key bits would not make des more secure. double des or triple des do.
which is also why it is believed that the NSA has computers that can break it by brute force in a reasonable amount of time, but nevertheless it is a brute force attack.
it has long been believed that a dedicated des-cracker is within the budget of extremely well financed organizations.
That's how I've heard (from various sources) the whole story with DES goes, and it seems like a reasonable one.
your story is pretty close to the spin i'm familiar with. peter