I think the Clinton/Reno thing was a bit different because they did it right after the inauguration, which is a perogative, and there's no evidence it was being done to punish a small group that wouldn't 'play ball'.
The real problem here isn't so much the firing, it's the other thing that's changed. The renewal of the Patriot Act contained a provision which allowed the replacements to be made without Congressional approval. Previously, US Attorneys had to be approved by Congress. Now, no such congressional involvement is necessary.