Thats a very good question, but with out a little more info it can be difficult to make a good recommendation. You gotta ask yourself what do want out of this lens? What do you plan on shooting? What do you enjoy shooting?
Most photogs are gonna have different definitions of what they consider "best all around". Ex: Due to my personal experience, i am hopelessly addicted to prime lenses, so IMO the 35mm f/1.8 that you have is already an awesome 'all around' lens because its fast, sharp and versatile. Of course you're not gonna be able zoom and to do a lot of nature shooting with it, but is nature shooting even something you want to do. See what i mean?
Now, you mentioned that you're thinkin about the 18-200 VR II so you may have already answered your own question. The 18-200mm is a fantastic walk around lens and prolly the closest to what some consider a 'can-all, do-all' lens... BUT the f/3.5-5.6 max aperture is going to have its limitations compared to something faster. But since you already have a prime in your bag, that zoom would be an excellent addition. So if thats the case, then there ya go! Id also consider the Nikkor 16-85VR. Doesnt quite have the reach of the 18-200VR, but its a couple hundred bucks less, has a quality build construction and im told it produces sharper images then the 18-200. And believe it or not the $250 Nikkor 55-200VR is actually a great lens as well! Sure its not as fast and it has a plastic mount, but it really does produce clear and sharp images! True story!
So really, i think you're on the right track. If at all possible, rent the 18-200 first and see if you like it before you pull the trigger on one!
Just my 2 cents