Sounds pretty basic, but is it possible that the choke mechanism is stuck? I had a similar problem a few years ago, blasted the whole mechanism with some carb cleaner, and it went away. Watched the choke slide back 2mm, and the whole thing was fixed.
Just a thought.
Could also check the idle screw on top of the EFI, just behind the throttle body. If it's running perfect now though, this probably is not your problem.
Dead bird get sucked into the intake, and took a few miles to burn it out?
Erik