One way that can happen is if you've moved the icon to a tab other than the one it was originally installed to. ipkg doesn't support moving icons and it can't find the icon in its new location while uninstalling the app.
Use Tab Manager to remove it.
Note: if you delete it manually from the shell or using file manager, as jdralphs suggested, Qtopia will still show the icon until you reboot (or restart Qtopia).
~ray