iPhone 3.1.2 is mostly bug fixes for problems introduced in iPhone 3.1 including the mysterious random shutdowns that users have dubbed "coma mode." Unfortunately, it doesn't appear to include a fix for the GPS bug.
It's a 241.7MB download the iPhone 3G and is available by connecting your iPhone to iTunes and selecting "check for updates" from the Info tab.
After installing 3.1.2, you'll also be prompted to install v.5.6 of the AT&T carrier settings:
Have you installed it? What have you found?