It's a common response when starting an exercise program for your muscles to retain water. It takes 3 water molecules to bond to each glycogen molecule, and this helps deliver energy to your muscles faster and helps them cope better with the new demands you are making of them.
Unfortunately, this increase in your lean mass can lead to little change in the scale even as you are burning fat.
However, muscle and water are considerably denser than fat, and typically this will result in inches lost, even if the scale is being unco-operative. And it sounds like this is pretty much what you are seeing.
You are right that muscle gain is a slow process (especially when you are running a calorie deficit to lose weight). This water weight is not really muscle tissue in the sense of the red fibery stuff, but it is lean mass rather than fat.
Put away the scale - the tape is a far more accurate measure of your progress.