Tips for Creating a Creamy and Smooth Sorbet
The general things that can cause icy sorbet:


Too much water Compared to other ingredients. Since you probably aren't going to take water out of your fruit, you pretty much have to add sugar or alcohol to compensate for this. This is tricky if you're improvising, and if the water content of the fruit varies.
Bad churning/freezing: This is mostly determined by the ice cream maker you have. It sounds like you're probably okay, since you get good results sometimes, but if the churning isn't good, you can get big ice crystals as it freezes around the outside before getting mixed well. If you're using the common type with a pre-frozen vessel, make sure you've frozen it thoroughly, so that you can churn long enough to smooth things out.
Chunky fruit: Big chunks will be really obvious, but even tiny chunks can help provide little bits that make the result freeze hard. Make sure that you puree well.
Too cold a freezer: sorbet is going to be best if it's not frozen extremely cold, but your freezer probably is nice and cold. Be willing to let it sit out a little bit before eating, or and perhaps keep it in the door where it's slightly warmer.


David Lebovitz has a good blog post about making homemade ice cream softer; most of what I've mentioned is also there, along with more details and some things that apply only to ice cream - for example, fat softens things too.