The problem with the Sacajawea Dollar, at the moment, is that:

1.) It's not different enough. It must stick out enough that everyone can recognize it a mile away. We need something like the canadian two dollar coin, only with a $1 value.

2.) mikemoto is right about this. The $1 bill is still out there, and the American public is so complacent with the $1 bill, they will not use anything different ($0.50 coin, $1 Eisenhower) until the previous thing is GONE. The treasury would have to force the issue, and stop all production of the $1 bill. This will ultimately save money as paper bills wear out after 18 months, but coins can last upwards of 30 years (coins from 1960 are still out there).

As such, the production of the Sacajawea coin has dropped considerably, and I'm not aware if it's still being produced (albeit in lower numbers), or if it's gone the way of the Susan B. Anthony.

As for Wal-Mart, they used to distribute the Sacajawea coins with every purchase at Sams-Club (they'd always give change between $5 increments as the coin), and at their local stores, but have long since stopped (last one I recall seeing was in really early 2000, and haven't seen 'em since then.