Changing permalink url structure

I’m porting my blog from Pivot to WordPress and noted a little snag in things. The permalinks on wordpress use hyphens instead of underscores (ex: whatever.com/recent-blog-post instead of whatever.com/recent_blog_post) Since I have over 1000 blog posts and fairly good search engine rankings I want to sort this out. How would I go about customizing that since I didn’t see any configurations in the permalinks admin and my mucking with htaccess just resulted in 500 errors from the server.