Cufon добавляет к создаваемым элементам класс, который вы можете стилизовать (полезно, если ваш содержащий элемент имеет отступы / поля). Так что для ссылки, просто используйте это:
a .cufon {border-bottom: solid 1px #000000}
a:hover .cufon {border-bottom: none}
Чтобы не допустить смещения ваших элементов вверх / вниз, либо добавьте границу к состоянию без наведения, либо соответственно отрегулируйте высоту обоих элементов ...