You shouldn't really have to uninstall the mandrake.
You can normally just install another distro over the top. But as for installing another distro because of modem problem's, well I'd say check out what kind of modem it actually is. Because if it's an unsupported "winmodem" then it probably doesn't matter which distro you try, it may be that it's impossible to get it working.
If it's an internal dialup modem then you should really find out exactly what the model is, and them look here
to see if it's listed as either having some support or not.
To explain, a "winmodem" is basically a software modem designed to run under window's, some of which have had drivers developed to work under linux as well (but some not). The route that I've seen recommended often is to lay your hand's on a proper (not winmodem) external modem and then config the hardware for you dial up connection, then just use a dialer.
If it's a broadband/adsl or cable modem then it's usually configurable under linux (though it's fair to say this CAN require some learning/digging for info).
Also if you feel that you have to install a new distro, check out the requirement's of the distro. That would be because distro's like mandrake can get away with just the one partition for everything, whereas, say gentoo doesn't seem to like installing to a single partition (it's default seems to be /boot, /swap and /root - and for easy of use/data retention reason's it may also be better to have a seperate /home).
Maybe this help's ???