that sounds exactly like the symptoms i'm having. the local shop had it almost 2 weeks, and they gave up today. I had the EGR flow insufficient and random cylinder misfire. I was have trouble starting the car. If i step on the gas, the car's completely fine, but if it idles it almost stalls out.
They thought the problem would be fixed by getting a new vacuum solenoid (under the MAF sensor), but that didn't work. The car's supposedly running really rich. I had them clean out the EGR valves first, but no luck either.
I'm brining it to Mazda on Monday.