Sorry to be the one to tell you, but, "Yeeeeeeeeees ... it does work". If you have done it more then 5 times already, and it still isn't workikng, then you are doing it wrong.
1) that you got the directory made correctly in the previous "mkdir" step, and
2) created the php-copy.sh script file (using the appropriate one for whether you are modifying a PHP4 or a PHP5 installation - since you are having trouble do not use the "more general script with options, as it will only confuse you),
3) and executed the "chmod +x php-copy.sh" command to make the shell script you created in step 2 (above) executable *
4) AND EXECUTED That "php-copy.sh" script by typing "./php-copy.sh" at the shell prompt(without the quote marks and where "" means "and then hitting the key"
Then, and only then, you will not get the ""Not Found -
The requested URL /cgi-bin/php.cgi/upload/index.php was not found on this server." message.
The fact that you are getting that message is "the strongest evidence" that you are not following the instructions, or are in some other way "doing it wrong". Doing it wrong repeatedly is not going to make it work any better...
So, at the risk of sounding like a broken record...
1) Re-read the instructions, and this post, carefully
2) Do it again, from the beginning.
If you are still not able to get it to work, then post back and report each step that you completed, and what results were shown on the screen after each action, and I'll try again to help you.
One last time...it works. It was worked for many many others; there is no reason it will not work for you if you do it correctly. If you can't do it correctly, it will never work.