How do I remove all traces of my Apple ID from a borrowed MBA? My MacBook Pro logic board needed to be replaced, so I borrowed an MBA from a coworker.

I restored the MBA from Time Machine to get back to work. When I was done, I removed my user account tied to my iCloud account, and gave it back. They didn't have much of anything on it, so he didn't care if it was restored to previous state (so he didn't have a Time Machine backup for this MBA).

My MBP was Mavericks, but their laptop was Mountain Lion. I offered to do the OS X update for them (as it was free) when I restored, but now I'm wondering if that was a bad idea.

He said that they are getting an iCloud prompt for my account when the App Store is attempting to do updates. They've signed out of everything they can find (system preferences, app store, iTunes), but they can't change it.

Any quick fix for this or do I need to pick up the laptop from them and do some sort of factory reset?
Apps downloaded from the App Store are tied to the Apple ID they were purchased under, and can only be updated with that Apple ID. From what you're describing, you must've installed some apps (licensed to your Apple ID) on his Mac while you were using it.

The simplest solution is to figure out which apps are licensed to you, delete them from his Mac (you can simply use the Finder to drag them from the /Applications folder to the trash), and then (if appropriate) purchase/download them under his Apple ID.