The "desktop" in KDE 4 is totally made over. Icons anywhere else can be changed exactly as you described, the properties has a button with the current icon on it.
But "desktops" are really now part of a concept called "activities." (great idea... buggy as all get out) and can be set to one of two options: folder view or desktop. When set to desktop you can't change the icon. When it's a folder view, it shows the contents of a folder you select.
You can change icons in folder view just like KDE 3. You can also add a "folder view" plasmoid that does the same; shows contents of a folder you select.
So what I have done on systems that need icons on a "desktop" to launch things, AND I want to use custom icons I do one of the two options above, ie set a plasmoid or set it to folder view.
But in either case I make a folder in the user's /home called "apps," and anything they want on the desktop, I put the icons in that folder. Mind you anything in that folder will be displayed on the "desktop" folder view, so only put the icons for apps you want displayed in there.
In both cases right click and unlock widgets. To set the whole activity to a folder view, right click the desktop, select desktop activity settings, go to the "activities" page and change via the drop down. (never forget to lock widgets after you're done!)
If you want a plasmoid to be a folder view, click the "cashew" on the lower right by the system notifications, click "add widgets" and look for the folder view.
Once you added it, click the wrench on the 'handle' that pops out when you mouse over, and change the folder it is displaying to the one with your desktop icons in it. The square thing on that handle lets you resize the plasmoid, this is preferable to making the whole activity a folder view. It can be made to fit whatever number of icons you have perfectly, eg no scroll bars.
BTW ubuntu/kubuntu doesn't do KDE 4 justice. If you want the best KDE 4 environment and the most helpful forum second to this one =) I recommend Mandriva. The current release is 2010.1, depending on your hardware it'll either be the greatest Linux experience you've ever had or you'll have a couple of well known, easy to fix issues... and a forum that really helps.
Hope this helps. Don't hesitate to ask for clarification. Welcome to LQ and don't forget to vote... for your favorite Linux applications that is, during the annual LQ survey.