Heh -- puppy long did better at wifi than anything save for backtrack for me. Also if you can spare a USB port (I know lots of laptops of that vintage like to drop it down to 2 ports so it might not be ideal) there are lot of rather nice N compatible wifi cards that are almost the same size as a lot of bluetooth cards (the raspberry pi crowd quite likes them) and will beat out the nasty miniPCI things they stuck in most laptops from around then. Likewise if you can (many will want one from a given manufacturer) you might consider replacing the miniPCI one.
When you say you tried debian and fedora what window manager did you use? They often ship with the beefier ones like modern gnome and KDE where something like XFCE or LXDE will scream along (or at least until you run out of ram using modern firefox, thunderbird and office stuff). Skype for linux leaves a tiny bit to be desired but it is usually not too bad.
It is generally better if you install them as you are installing the OS (or if the OS comes with a respin for that window manager) but if you can be bothered to deal with the fallout (usually not an awful lot beyond adding in management tools if it did not come automatically and changing the terminal colours). Install them as you would install any other program, usually best to let it do its own thing when it comes to suggested extras, and then you can select a new one at the login screen.