Have you ever seen Full Circle Magazine? It has articles, pictures, How To's, etc. What if LinuxMint had something along these lines? Maybe have articles about new features, development, community editions, interviews, How To's and some nice graphics. Maybe use the pdf format for distribution? There are always new and improved tools going into Mint releases, a magazine might be a good way to advertise all of the improved usability features that are incorporated into Mint.
Our community editions could be featured with highlights of the features they contain. There are a lot of good features that go un-noticed in reviews. Have articles on how to work around important issues, like the Intel issue and things like that so people are more aware that these things can be fixed. Maybe have something about what goes into the making of our releases and how they differ from the base they are built from. Maybe feature some articles on creating artwork, we have some very talented artists in the community that go above and beyond to help others.
Maybe interview some team members so the community might get to know them a little better. There are plenty of sources of interest to write about and including some screen shots would provide a nice professional look.
Our best promotion will always be the quality of what we release and the community that supports us. This is just a rough idea but with the right people it could help promote Mint in a big way.