Your ratio of dogs to personnel is a little misleading. It is relevant to note that there is pretty much no use for dogs in the Navy and Air Force. There are 460,000 + 182,000 = 642,000 active duty personnel in the Army and Marine Corps.
Furthermore, most of the Army and Marine Corps are flabby support personnel (dirty POGs). To get a semi-reasonable count of the units that can actual do fighting (not counting air units who don't have much use for dogs either) lets count up the Brigade Combat Teams for the Army. For the Marines it is more complicated because the relationship between MEF, MEB, and MEU is not fixed, but we will try to sum the strength of the Ground Combat Elements.
For the Army, there are 32 brigade combat teams at a strength of 4400 soldiers each for 140,800 actual soldiers. Estimating 73 battalions at 900 Marines in the 4 Marine Divisions combined, we get 65700 Marines. This means a total of 140,800 + 65,700 = 206,500 total actual combat troops. Taking your number of 2500 working dogs the ratio is more like 1:83; a lot closer to your target.
To close the gap, the only thing we need is a bit of culture change. From conversations with several brothers/college roommates who have been infantry officers in both Iraq and Afghanistan, everyone wants more dogs.
First off, Iraqis are generally terrified of dogs (see Abu Ghraib). So there is that.
Second off, when there are bad guys in a building, and you want them dead, but there are women and children in the mix, dogs are a great option. They are trained to go after people with guns, so they are much less likely to kill women and children (especially compared to, say, artillery).
Third, after I expressed incredulousness at the notion that dogs are so effective as manhunters, my friends informed me that guerilla fighters are generally unprepared to deal with a dog. They don't wear protective clothing (camo with tough fabric is a big help if you are being bitten), they don't have training in hand to hand (or hand to dog) combat, and since they are fighting soldiers, they tend to have guns instead of knives. Guns, however, are much less useful than knives in a small room with a 120 lb German Shepard hanging on to your arm.
In any case, consider that anecdotal, but if your army is primarily into anti-insurgency warfare dogs are a pretty good deal, no genetic engineering required. If the generals actually listened to the JOs (or, heaven forbid, the NCOs) there would probably be more dogs around already.