I have no idea what to recommend. How much dough are you willing to spend and what do you want: a wood board or what?
Check out these links: http://www.uscfsales.com/
http://www.thechessstore.com/c=u2fssX9WfS3Wk8HL1HVaJMWhW/category/00016-chess-boards/
http://www.thechesszone.com/chess_sets_sizing
http://www.chessusa.com/category/CHESS_BOARDS.html
Thanks for the reply! I was hoping to spend around $30-$50 which is the price range of this set. It doesn't matter if the board is "new" or "used" as long as it is in great condition.
I was hoping to get a stone, marble, or metal board since the pieces are made of a stone resin mixture. A pattern or design on the squares or around them would be nice. Something with a medieval, gothic, or medieval theme would be fun! 
-=- Boris
If you ever happen to find yourself in Progreso, Mexico on the Yucatan penninsula, they have shops all over the place selling stone chess sets & boards. I don't remember ever seeing boards without pieces for sale, but the large sets go for around $35. The picture in my avatar is just such a set. They make them out of quite a few different kinds of stone so many different sets to choose from.
Of course I don't recommend going there just to get a chess board, but there is a cruise terminal there, and if you happen to book a vacation cruise with Progreso as one of the stops, you're all set.
Where do you live? Have you checked out local dept stores, gift shops etc?
I recently bought a cool Barbarrosa themed chess set off of eBay. The pieces are ivory and black/red and they are made from a polyresin type of material. A board was not included in the sale so I am now on the look out for a matching board. Finding one is proving to be difficult. I was wondering if some of you folks here could recommend a nice matching board.
Here are some pictures of the pieces.
The bases are approximately 25mm and the king is 60mm high. A medieval or renaissance theme board would be great!
-=- Boris