Firstly, for the old URLs to disappear, you need to redirect them to the new ones as phranque said above.
WebmasterWorld has the HTTP Response Status Code Check Tool [freetools.webmasterworld.com] which you could use for the redirect check. Go to that tool, enter your OLD URL and click on [Check].
The results you should be seeing are something like this:
http://www.example.com/old-url - 301 Moved Permanently http://www.example.com/new-url - 200 OK
If you are not seeing the 301 code next to your old URL, then your redirects are not implemented properly and in this case Google may hold onto old pages.
You said that you have changed only 4 URLs. Once you set up your redirects, then it will depend on when Google crawled the old URL in order to see the redirect. As phranque said, check your logs to see if old URLs are crawled by Googlebot and if they are, then give it up to a week for the index to be updated.
... and a further week for the information to trickle back to wmt. The "Index Status" area of wmt officially updates once a week (mine does it on Sunday), with a delay of an additional day or so before the most recent numbers kick in. And don't be surprised if some numbers continue to change retroactively for several weeks into the future.
It could take maximum 2-3 weeks to crawl a big xml sitemap. You can also place 100 or so links in a page and Add to index -> submit. In that case Google will crawl all the links in a day. So can make 500 requests in a month.
You also need to 301 redirect any request for example.com to www.example.com or Google considers it as duplicate content. They really consider it as two sites that are identical. If you can go to example.com without www.example.com showing in your browser's address bar, it is not being redirected.