I had the same problem, and it drove me crazy until I worked around it by enabling push.
As the commenters pointed out, the settings don’t really make sense. The relevant settings are under “Mail, Contacts, Calendars”, “Fetch New Data”. I found that even with the big “Push” switch enabled, it didn’t really push contacts or calendar events when the apps aren’t running — it would fall back to the Fetch setting below it, which I had kept set to Manually since 2007 to conserve battery life. Once I changed Fetch to “Hourly”, the problem was “solved”, I guess.
But it really just seems like Dr. Drang and I aren’t receiving proper “push” data when the Phone and Calendar apps are closed. I assumed it was a bug. I sure hope this isn’t the intended behavior.