Bear in mind that the patch won't work by just running it, unless you happened to change the installation folder to "Sid Meier's Civilization 4" instead of the default "Sid Meier's Civilization 4 Complete." The problem is that Complete uses the latter folder name by default, and the patch is set up to look for the former installation folder. Since it doesn't find it, it creates a new path of folders and the game isn't patched.
That doesn't matter one bit. The patch finds the folder by looking at the computer's registry, not by the actual folder name. The registry will have the location of the game, and the location of every single program on your system, stored in it's database. When I install the game I drop the Sid Meier bit and simply call the folder Civilization 4. By your reasoning the patch shouldn't be able to find the game but it has no problems. You really should learn how computers work before spreading bad advice.
I read that several others here had problems getting the patch to install, and it was creating a different folder. When I installed the game, I noticed it was going to install in a different folder, so I changed it, and the patch worked for me, so I thought that was the problem. If it would find the location of the exe anyway, I wonder why others had problems with the patch.
This thread has some people who said it was creating a different folder: http://forums.civfanatics.com/showthread.php?t=286835
What kind of an error? IIRC, Civ Complete only comes with patch 3.13, so you still need the latest one.