That's kinda true, but there was a natural nuclear reactor: http://en.wikipedia.org/wiki/Natural_nuclear_fission_reactor
Also, the Sun seems to work pretty well.
If course, neither of these evolved though biological mechanisms, though, but they did arise in a natural environment. I find it difficult to imagine circumstances under which evolution would "figure out" a nuclear bomb - ie, I'm agreeing with your point that evolution usually requires a series of gradual refinements rather than a big jump forward.
Also, all a nuclear bomb requires is enough fissionable material in a small enough space that the reaction is run away. I see no reason to suppose that a spot particularly rich in uranium (or other such materials) couldn't get squeezed hard enough to explode, or that a critical mass somehow formed by natural processes (particularly those which put it under very high pressure).
I suspect that the reason we haven't observed this happening is because most of the material is not present in concentrated form and because it decays over time.
But just so you know, people have accidentally assembled critical masses by hand. There's no special magic to it, other than getting a large enough quantity of suitable material in the first place (which is really, really hard). You can read some of the scary things that happened here:
They called it the "demon core" after a few people died working on it.
The nuclear bomb was a needlessly confusing example--I could have just mentioned explosives in general. Evolution is all about weapons, and explosives make for damn good ones, and it's not hard to imagine a realistic organism that uses them, unlike a nuke-wielding organism. Only I'm not sure that no organism uses explosives. I was already wrong once today about what nature can't do!