Changing Permalink Structure Results in 404 Errors

Hi everyone – wondering if I can draw on the brilliant minds of other WordPress users.

I’m helping a friend with his website, and I want to change the permalink structure to a custom structure:

/%postname%/%post_id%

Seems simple enough to do – except once I save this, I try to navigate to his site and I get a 404 error. In fact, any URL structure other than the default results in a 404 error.

Any ideas on how I can get around this?

Not sure if this is related, but we’re using Thesis as a theme.

Thanks for any help!