Hello, thought I would post my process for (finally!) fixing this. If you want to copy my process, make sure you have the exact same OS:
I am running XP pro (32bit) SP3 on a custom box.
Originally, I downloaded normally to F: drive (which is my boot drive btw), got the error immediately upon opening. Tried un/reinstall to no effect. Then tried installing C++ which I don't think I had before (point of interest, if you need this, make sure you download the 2010 or latest version for your OS and get the x86 version if your OS is 32 bit, this can be confusing as there is a separate 64bit version) and dot net framework v4. No dice.
Finally, I decided to uninstall everything, including dot net and C++ (which it turns out I had multiple versions of in my program list), neither of which had I uninstalled previously. I reinstalled starting with dot net--this time v3.5 as v4 is in beta currently (though I've read that LOL is supposed to work with either). Next I reinstalled the 2010 C++ x86 redistributable package. Finally, (and as it turns out, using the same setup files I originally downloaded) reinstalled LOL. Also at this time I tried that DNS trick (using 8.8.8.8 and 8.8.4.4 as my default and additional DNS servers) with a quick DNS flush and restart. When I logged back into windows, LOL started up like a charm. No further issues.