Inline hints about something new are nice. The good ones don't get in the way, but provide an entry into an explanation of what has changed.
The important thing is, no matter how you want to present your information, I need to be in control of when and where I dig into it. Your changes may not affect what I'm trying to do right now, I might be in a hurry, or I'll just figure it out myself, etc. You cannot judge what I need to know. This is what annoys me about big updates like the Google Plus one recently. Big fly-out thing trying to get my intention about whatever they changed, but it just gets in the way and it's not like it's complicated anyway. Well, to me. Others might like that. But you got to cater to everyone.
This also means I need to be able to get to that information later if I don't have time for it now.
All those different ways of telling users about what's new are good, but it depends on what changed. If you relabeled some stuff you could make do with a little tooltip, but some workflow changed might need a multi-screen walkthrough.
Why not, along with inline notes, have a little update indicator somewhere in a visible place I can click on to review what's new? List whatever is new in a single place I can look for updates, and allow me the option of reading more, or going into full walkthrough mode or whatever's appropriate. That's what I like about the update indicator for the iOS App Store. It's a single indicator, always in the same place, and clicking it gives me an overview of what's new. Usually I'll not care, but I can chose to read more. So, if I missed an inline thing I could always refer to that central indicator and get to the update information.

download bmml source – Wireframes created with Balsamiq Mockups
sorry about the crappiness of the mockup