Another possibility is to keep the 18-55 and complement it with a 55-200 VR. There is also a none VR version of the 55-200; I suggest that you avoid that version.
As to your original suggestions you might remember that the 18-135 is not a VR lens. The 18-200 is VR and was well thought of after taking into account the very ambitious specification. My own 18-200 has drifted out of adjustment and now front focusses. This is not a problem for me because I have set my D300 to compensate for the error. The D40x does not allow for such compensation. I understand that this fault is more common than it should be.
I guess all that is not very helpful since it raises more questions than it answers. Given that you already have the 18-55 kit lens I think that buying the 55-200 VR is the best option exept that its closest focussing distance is 1.1m and will not be any good for insects.