I don't think changing your logo matters very much for us. Wal-Mart did it *shrug* and yeah, they are big enough they can - my argument is that you're small enough that you can as well. Anything in between probably shouldn't change.
That being said, provided you stick with the same basic theme so the new logo actually looks like a refresh of the old one, (which yours does) and not a completely different logo, you still have the same basic colors, the pants, etc... then it should still be a recognizable brand by your clients. EDIT: heck, look at the Microsoft Windows logo for example. Changes every release, and still it's basically the same logo as it always was; just they gradually altered it over time. Despite all the changes over the years, it's one of THE most recognized logos in the world...
I recently made the call to refresh my old logos and it is one of the best things I've done. I worried about brand recognition at first as my new logos are drastically different, but I figure I'm small time enough that I should probably change now, before I grow any and it's too late...
Just my 2c.