Couple of things come to mind.
Assuming you are on ADSL
You mentioned that you have changed ISP - did you have a faster connection with your last ISP?
Also, have you checked your line to find out what speed it does support?
If you are comfortable with logging into the router you will be able to find the stats for your telephone line. If you can post them, S/N margin, attenuation and sync speed we should be able to look up the theoretical max for your line.
Have a look here for a good speedtest
Broadband » Test it » Fix it » Boost it!
And here to check the max line speed for your postcode
Broadband Line Checker - Broadband Finder
Let us know how you get on