Free Shipping is not supported in the free community extension Matrixrate. The reasons for this are that the maintanance of the extension across Magento Versions would be difficult and costly. We therefore have taken the approach of only offering free shipping support in our paid extensions such as Premium Rate.
If your products do not have weights set then Magento shipping in general will produce unpredictable results. Certainly Free Shipping will not work. To resolve set a weight on all products.
In Shipping Method configuration make sure you select the Free Method that free shipping must apply to. For example with UPS select UPS Ground when you require free shipping to apply to Ground shipping only. Without this Free Shipping will not show
If you do not see Free shipping appearing on a shipping carrier a quick test is to see if when the 1 item you wish to have free shipping on is in the cart does Flat Rate shipping show as Free Shipping. This works for simple rules only, but does give you a sanity check. If you dont see free shipping then you have a problem with your promotion rule.
Please switch on Magento tablerates and ensure you can get both free shipping to show and can checkout. A simple tablerate csv can be found below. If you cannot then this points to an issue elsewhere in the code, and unrelated to the WebShopApps extensions. If necessary completely disable WebShopApps extensions to eliminate them and then see if you still get the issue.