Description of problem: Don't use just color to differentiate between installed and not installed packages. This is accessibility issue. If you are going to use color, provide a additional hint besides that. Checkboxes are commonly used for this.
Yes, somebody else mentioned that. Should the checkboxes go to the right of the text, or to the left or right of the icon?
In between text and icon
Richard, you can look at what pirut does for ideas. Not that I think that the pirut approach is very clear...
We can also ask mike to give use some better installed/uninstalled icons.
Better icons are in rawhide now