I loved "A First Course in Abstract Algebra" by Fraleigh. It was a while ago, so I don't quite remember whether it had solutions for the exercises or not.
[edit]: There's also Michael Artin's "Algebra" which is somewhat dense (certainly without solutions), but a very fascinating read due to its emphasis on symmetry groups. Particularly useful and enlightening in the context of modern particle physics.
Fraleigh contains solutions to the odd numbered sections (7th edition). It was the text I used (and enjoyed). I still have a copy of it, three years later.
[edit]: There's also Michael Artin's "Algebra" which is somewhat dense (certainly without solutions), but a very fascinating read due to its emphasis on symmetry groups. Particularly useful and enlightening in the context of modern particle physics.