Simon Singh books. Great read. Can't go wrong. Go get 'em sista.
The Music of the Primes is a decent read. Having said that, I ne'er finished it. I can't even remember why.
I wouldn't recommend books by Ian Stewart, as much of a legend he is (I'm, like totally not biased being a Warwick graduate). I'd certainly read Amazon reviews or something if one does take your fancy. I read one and used another as reference material for an essay I wrote, and both kinda bored me.
Random fact: I knew an answer to a question I was asked in a Cambridge interview because I'd read Fermat's Last Theorem. It discussed how you can't cover a chessboard with 2x1 dominoes if you remove two opposite corners.