Ah, you're on LLU, then

[FAR better than Connect]
Speed won't have changed when you went from Free to Unlimited: Both have the same
upto speed (20Mbps), the difference is in the usage limit (2GB versus unlimited). Not at all pricey, btw - £7.50 for upto 20Mbps with truly unlimited usage is very good.
If you have speed issues, it may be worth starting another thread in the
Other ISP forum. A lot of speed issues are simply down to the person's own line... it can just be that it's too long for a decent speed, and/or the internal wiring in the house may be causing issues (e.g. bad extensions causing noise on the line).
Regarding the Sky+ box... If you can't get Sky to sort it for free, via threatening to leave (& the trouble with calling their bluff is that sometimes it backfires!), you could have someone come out & deal with it... it used to be £65 for a callout, IIRC. That covers everything. Not sure if it's the same still. Or, as Paul suggested, maybe it's time for an HD upgrade?