If you've only had it for a few days then yes, I would get it swapped straight away.
If you've had it for a while and it has only just started freezing then it might be worth thinking about what might have changed to cause the problem - for instance, did it start after you downloaded a new book? This may be a sign of an indexing problem. To check this, search for a nonsense word (xgdfehxsa or something like that). If the search results show there are unindexed books, try again in a few hours. If it still shows unindexed books there may be a problem with the book, try downloading it again.
Unless you can find something wrong fairly quickly I would contact Kindle Customer Services (
http://www.kindleboards.com/index.php/topic,73465.msg1181468.html#msg1181468) and discuss it with them.