water backs up into both sides of the sink when the dishwasher first starts to drain. I do not have a disposal and I do have an airgap. Sink drains were clogged but just had that issue fixed. Water now drains just fine and no longer backs up. What might the issue be with the dishwasher water backing up into the sinks.
In addition, if you do have a waste disposal unit the dishwasher drains into it in the disposal chamber so if it has any waste in it, it will prevent the disposal from draining the dishwasher properly.
My parents have this problem in their kitchen sink. They don't have an air gap device (though that's mainly to ensure that wastewater draining from the sink doesn't flood the dishwasher, and IME it causes more problems than it solves when you're trying to clear a blocked drain) and the drain normally runs fine, but when the dishwasher is pumping water it will outpace the drain, to the point that if that sink is stoppered with a full basin of water, it will pop the plug and push dirty dishwasher water into the basin.
It's all about relative flow rate, and exactly how the drain is designed. First of all, the fact that both basins fill when the dishwasher is draining tells me that there is a flow obstruction beyond the T-junction of the two drains. Either that, or some yahoo calling himself a plumber put the T-junction in backwards (if that's the case, filling one basin and pulling the plug will cause the other basin to fill in a similar way). I'd call in another plumber and have him scope the drain to make sure there is no remaining blockage that could slow water drainage.
Additionally, if you have a disposer, even if it's clear at the time the dishwasher is draining, I've seen designs where the way the dishwasher drain feeds into the disposer creates a backwash that slows draining (this appears to be the problem with my parents' setup). It is often possible to feed the dishwasher line into the drain in other ways; you might look into rejiggering the line to bypass the disposer (just make sure you cap the dishwasher inlet on the disposer or you'll have a huge mess the next time you drain that side of the sink or run the disposer).
While you're at it, check your tee. Some tees have a divider that separates the "direct" flow moving straight down from the flow coming in from the side. The basic idea is to prevent a backflow of water from one sink into the horizontal drain run for the other. In my opinion, however, the design has few advantages and many disadvantages. It doesn't aid venting, and it obstructs half the pipe's diameter which restricts the flow rate through each drain and causes easier clogs especially on the disposer side.