Did this just start happening after the tune-up work? Every car I've ever had that did that had a vaccuum leak, but it could be something else I suppose. The fact that timing has no affect on idle speed could also indicate a vaccuum leak. Is it possible you bumped a line loose when you were replacing all them bits?

A likely source of a vaccuum leak might be the brake booster, or the one way air valve for the booster. First, try disconnecting the booster and plugging the hole. If that smoothes it out...at least you have isolated it.

If that works, install a new one way air valve first. YOu should be able to find one that installs in the middle of the line. You can leave the old one in place. If that doesn't do it, you may well have a bad brake booster.

Just a thought... good luck with it!
-Matt