There is definitely a chance switching ISP's might help. Of course it may be worse. Depends on several factors. One factor is on your end. If the line quality on your end is poor then no matter who you sign up with you will not get optimal speeds. One way to test this is to try to dialup with your hardware from a different phone line, prefereably one that you know can get higher connect speeds. Otherwise you may need to contact your telco provider and see if they can do line quality testing for you (some may not do this or may charge you for this service).
Besides line quality, the other most common reason for poor connect speeds is incompatibilities between your modem and your ISP's. You should consider upgrading the firmware on your modem to the latest version. Even if this is a new modem it still may be a good idea to check with your manufacturer's website to see if a newer firmware is available. This may help with compatibilities assuming your ISP also updates their RAS box modems on a regular basis.
In short, you should do what you can on your end first. If that doesn't help try a different ISP.