Due to the extreme slowness you're experiencing, yes, I'd suggest doing that. Of course, this will erase everything now on the drive. So, backup what you want to keep, before proceeding with this, if possible.
If you do a clean install and experience poor performance right away, I suggest you download memtest and run it to test your memory. If software issues are not causing your problem, you apparently have hardware issues. So, a memory test may be well worth the time. Another test would be to remove your old memory and try running it with only the new 512MB module you bought.