I'm not quite sure what could be causing this issue, we have absolutely NO extensions or modifications. This happens on a fresh install with one product made being the only change.
It doesn't matter if we're in the the RWD theme or the modern theme. When clicking "place order" the order submits in the backend of Magento, the button disappears for a second and says "submitting order" and then the Place Order button shows back up. No forwarding to the success page, this causes people to just click "place order" over and over, and it submits a new order every time. No theme will take us to the success page.
Best Answer
Solved! Magento was lazy with their changelog and lazy with not updating their magento-check.php file.
1.9.1.0 requires that your server has php-mbscript (mbstring) enabled in Apache.
Go into WHM or whatever your server software is and enable it and your checkout will work.
Would've saved me a lot of headaches if they just came out and said this.