Just noticed this myself.
"Recently added' no longer works at all on my iPhone: I get a random selection of NON-recent songs. Maybe it's using the date the songs were copied to the phone, rather than the date from iTunes. A definite bug, but unchecking Live Updating was a helpful tip.