in short this is normal … i guess you added stuff to your .htaccess file between the # BEGIN WordPress and # END WordPress
What happened when you changed the permalinks is that WordPress changed that section of the .htaccess file.
So you need to open and insert the rewrite rules into your .htaccess file – BUT not between the WordPress tags
I hope you have a backup copy of the old .htaccess file?