How To Switch Permalink Structure In WordPress Under Ubuntu
There are certain things you need to tweak in Apache running under any Debian platform (including Ubuntu) in order to have it properly redirect webpages (301) after you change your permalink structure in WordPress.
Read more at HowtoForge