None of my custom permalinks structures are working.

Make sure you don't put a trailing forward slash after your permalink structure. This was affected by changes in WordPress 3.4. So, if your permalink structure looks like this: /%postname%/%post_id%/ you should remove the trailing forward slash so it looks like this instead: /%postname%/%post_id%