Drupal 7 on new Linode stack, POST/GETS 404ing but pages still loading?
The reason for this is most likely that clean url's are disabled. Make sure that mod_rewrite is enabled in Apache.

Fetching pages still works, because the 404 triggers Drupal, which is then able to return the correct page. That does, as you found out, not work for form submits, because the submitted data is lost when doing the redirect.