I have the same problem. I've tried running various Windows applications (Quicken 2008, Internet Explorer, Microsoft Word), but no icons appear in the main area of the dock. Coherence otherwise seems to work fine. When a Windows application is minimized, an icon naturally appears on the right side of the dock (or bottom part of the dock if your dock is on the left or right). I believe this is the icon that the previous poster is referring to - when you right click on this icon the only option is to restore (Open) the window, as you might expect.
But the "Coherence" icons are missing, and hence a user can't right-click on the icon to keep it in the dock for future use.
I have tried uninstalling and reinstalling Parallels Tools, twice, with no effect.
I upgraded to Parallels 4 over a Parallels 3 (5626) installation. I am not using Boot Camp. The Windows guest OS is XP Pro SP3 with the latest Windows updates. The installation is very plain as I generally only use it for Quicken.
Mac specs: Leopard 10.5.5, Intel iMac 20" Core Duo 2.0 GHz (Early 2006), 2GB RAM