These materials already exist and are called auxetics: http://en.wikipedia.org/wiki/Auxetics.

One notable example is the material that makes up Gore-Tex. My materials prof talked about being in a lab that had a cube of it and how surreal it was to have it act this way.

There is already a company that produces auxetics commercially for some of the applications mentioned in the article: http://en.wikipedia.org/wiki/Zetix.