Thanks! The story I got is that they are replacing all of the injectors. I'm supposed to get it back tomorrow, so I'll post an update if everything is back to normal.
I also forgot to mention that it takes longer to start up with the engine turning over more times before it starts, and a few times this week I have felt a mild shuddering at idle when it is rough. From that I guess it makes more sense that och is right about the fuel pump.
Also, the black soot is much heavier on the left (driver) side exhaust, and there is a more pronounced gas/exhaust smell that wasn't there before. My symptoms are very similar to this post
http://www.bimmerfest.com/forums/sho...d.php?t=657057 except without the change in mileage or the gear change surging.