The answer is yes. I generally put my navigation into unordered lists and then use CSS to style them. Most of time I use button like images behind the text and I don't actually replace the text. However, I have had to use these techniques to replace each link with a different image, and even include mouse over effects on those images. Lots of work, and only done when I cannot convince the client not to.
At any rate, it can be done.
One of the main reasons that this technique has an effect on SEO is that text on the page carries more weight than text in the alt attribute of an image.
Glad I could help
