Per "cambiare colore" all'incona basta che crei un'immagine che rappresenta i due stati del link (normale e over). quindi con due colori diversi. L'icona è sempre contenuta come sfondo nell'area del link. Dato che l'immagine è sempre posizionata come sfondo del link, ti basta modificare il valore di background-position per spostare l'immagine nella direzione che vuoi quando ci passi sopra col mouse. Quindi, dato che l'immagine è alta (o larga, dipende da come la fai) il doppio dell'area del link, mostrearà sempre una sua metà, che sarà quella relativa allo stato normale o over.

Cosa usi per la struttura dei link? Un elenco non ordinato (<ul>)? Se è così (ed è la struttura corretta in XHTML per un menu), basta che dichiari display: inline gli elementi[*], oppure puoi dichiararli float: left (meglio, perché così li trasformi in elementi a livello di blocco che sono più gestibili dai diversi browser).