I haven't played with the Nikon Coolpix, but I did have the Kodak EasyShare (CX7310) - and we recently upgraded for the same reason.
The key to good photos is firstly the MP rating, and then the Optical zoom rating. A lot of people get tricked when they talk about 'Digital Zoom' - which from the camera you would already know is just cutting down the view frame without actually improving the image.
The best combination is as follows (only from my experience & disregarding digital zoom):
No Optical zoom - minimum of 8 - 9 MP
3 x Optical zoom - minimum of 6.5 - 8 MP
5 x Optical Zoom - minimum of 6 - 7 MP
10 x Optical Zoom - minimum of 5 MP.
Myers (in Australia) recently had their post Xmas sales, and we picked up the Sony Cyber-shot (with 3 x optical zoom & 7.2 MP) fairly cheap - and it is awesome. You wouldn't believe the difference spending a bit of money on a camera does!
The Nikon Coolpix 4600 is unfortunately only 4 MP, so you are really not going to benefit too much, however it does have a 3 x optical zoom, so the quality will be markedly better than the Kodak.
I would shop around with those guidelines and try to get yourself the best deal. For example, there was a 10x optical zoom at 6MP which would have taken better piccies than the Cybershot, and it was $AU150-200 cheaper - the reason is that it was not a compact ( which are popular at the moment ). So you really need to figure out also what you want from the camera...
Hope that helps!!