That's insane! I get the opposite with my ISP: I started out with a speed of 5MB and they've gradually upped it to 8MB for free. 60GB usage (combined up/down) per month, too.
You really do need another provider, it seems. That's incredibly restrictive, especially if you're paying for a decent plan. I bet they're going to lose a lot of customers.