Treadmills used to be fairly notorious for knocking out ADSL connections, but I haven't seen it mentioned recently. If the treadmill is new, I would take it back to where I bought it and demand a refund. Electrical equipment has to conform to interference regulations, and I doubt that your does (although I admit to knowing nothing about the subject).
If that isn't an option, then I suppose that you need to determine whether the interference is mains-borne or radiated. If the latter, then you might find relief by moving the treadmill as far away from the router as possible. If it's mains-borne, then an interference suppressor might do the trick.