Similar, though more complex, problem here. My Time Machine backup also got de-associated or de-linked from my Mac within the last week. My case was more complex, since I had to mess with the firmware on both my Airport Express and Airport Extreme to get AirPlay/AirTunes working after an Extreme firmware update bricked it (hey, I said my issue was more complex). Anyway, I got that other problem resolved but now the Time Machine backup is stuck on February 2, the last time I did a successful TM backup. I can't seem to update it.
My hardware configuration is a USB hard drive connected to the Airport Extreme. I googled this issue, and read second-hand reports that Apple does not now support my configuration; in other words, the supported configuration for Time Machine, other than an Apple-branded Time Capsule's preinstalled hard drive, is a USB hard drive connected directly to the Mac that's being backed up. I actually still haven't tried connecting that USB drive directly to the Mac yet, though for various reasons I'm not really expecting that to work with my existing backup, which I suspect to be sort of fried anyway. I'll report again if I learn anything new, but going forward I plan to just connect the Time Machine backup drive directly to my Mac.
Longreply was long.