The issue has proven link to Google Page Speed service, as Bob discovered. When disabled in application console, the redirect works ok. When re-enabled, it fails again.
The issue is **observed** on production application with PageSpeed, **VIP SSL**, Google Apps domain authorization, Google Apps data set to store in **EU** Data Centers only.
The issue is **not observed** on testing application with PageSpeed, **SNI SSL**, Google Apps domain authorization, without EU data location restriction.
So, the SSL settings may also play role, as johnP noted.
As a temporary workaround, we commented out *secure:always* for the site entry url's in *app.yaml*, and decorated their handler methods with
https://gist.github.com/3974365.
There's also stack overflow question on this topic, if you have similar issue, or look for solution.