A deck will typically fan like a dream right out of the box until you give it a few shuffles at which point individual cards interact with the oils on your hand, creating clumping. The more you work a deck in, the more evenly these oils get distributed and after a little while, the cards will once again fan beautifully with just a little bit extra pressure to get it even.
I had the same problem with the S&M decks and most cards, really, and from my experience you'll get the best fans when a deck is worked in.
Also depending on where you live, humidity may be causing the issue (or lack, thereof). Keep handling the deck, work it in, and I promise you the cards will fan great again in no time!