die Farbe der Unterstreichung allein kannst du nicht ändern. Du kannst aber einen ähnlichen Effekt mit Rahmen, deren Farbe du über border-color modifizierst, erreichen.
Jein - man kann das a-Element auch in ein span-Element verfrachten (oder umgekehrt) und unterschiedliche Schriftfarben verwenden um einen entsprechenden Effekt zu erzielen. Mit CSS3 wird das wohl auch mit ::outside funktionieren, ohne dass man ein zusätzliches Element einfügen muss.