I previously (happily) used DIA for any UML diagrams, before I got Visio, and while Visio is good there are some UML 2.0 compliance issues that are driving me crazy more and more. (Nested states, and entry/exit points for states???)
Anyway, been doing some digging and thought I’d share the wealth:
DIA: http://projects.gnome.org/dia/
UMLet: http://www.umlet.com/
Violet: http://horstmann.com/violet/
ArgoUML: http://argouml.tigris.org/
StarUML: http://staruml.sourceforge.net/en/
Most of the above are cross-platform in one form or another.
-B.