The minifig scale dog has only been made in 2 colors--new dark gray and new brown.  LEGO presumably started making the dog piece to be The Grim in the Harry Potter sets, because the dog piece first showed up in 2 Harry Potter sets in 2004.  In the movie (and maybe the book too; I don't know), the Grim dog was dark gray or black.  The 2 Harry Potter sets that have the dog both have it in blay.  Now there are several colors that would work for making a LEGO dog, of which blay is probably not the worst, but neither is it the best.

As soon as the LEGO dog came onto the scene, people wanted it...they really wanted it.  This pretty much holds true for any new LEGO minifig-scale animal.  Blay is by no means the adult LEGO community's favorite color, but as for the dog piece, when it first came out, it was the only choice.

In 2005 LEGO made a new brown dog.  It came in the Police Station set.  When this new dog color came out, it was instantly more popular (and therefore more expensive) than the blay one for 3 basic reasons:

1. Any part in a new color is "cool".

2. New brown is a better color for a dog

3. The new brown dog only came in one $70 set, making it rare

When the 2005 Advent Calendar came out, it had 2 blay dogs.  When that set later went on clearance for a scant $5 on Shop@Home, I'm sure that many Bricklink sellers (including myself) saw what a great deal that was and bought as many as they could before LEGO ran out.  Thus many more blay dogs came onto the secondary market, while the brown one remained rare.  When I put some blay dogs onto Bricklink at the beginning of 2006, I remember seeing that the brown dogs were going for almost double the price of the blay ones.

Just today I took a look at the prices of blay dogs versus brown ones and was surprised.  Brown dogs are much cheaper than blay ones.  There are still a lot more blay dogs on Bricklink right now than there are brown dogs.  If you look at the sale history for the past 6 months, however, there have been more brown dogs sold than blay dogs.

I think I may have a theory as to why the brown dogs got so cheap.  In 2006 LEGO started putting 2 brown dogs in the Community Workers minifig pack.  The LEGO site has a feature where you can view the top selling items each day.  (It used to show the top 30, but now it shows only the top 20.)  I remember that the MF pack was on the upper half of the top 30 list for a loooooong time.  Minifigs are highly sought after pieces that also have a good resell value, so it's no surprise that the pack sold well.  I believe that many AFOL's out there who wanted dogs bought some when blay ones were either the cheapest or the only ones to be had.  Now that the community's new-piece appetite is partially sated, and the brown dogs from all those MF packs have trickled down into the market, we find a role reversal for the demand and price of brown dogs.  The fact that the MF pack is the only set with a dog that's still available for sale also drives down the price of brown dogs.

It still doesn't make perfect sense to me, but that's my theory.  Now if you'll excuse me, I'm off to buy some brown dogs. Dog

UPDATE: Michael Huffman has informed me that the brown dogs have appeared in Pick-A-Brick.  I do believe that that's the missing piece to the puzzle.