First, did you use the correct version of the patch? There are two; one for 1.39 and the other for 1.5. If you're sure you used the correct version then it's likely you pasted it in incorrectly. Make sure you didn't accidentally truncate it, and make sure you don't have extra spaces at the top or bottom. Use only a plain text editor to do the copy/paste.

PS: Also check to make sure you're not using table prefixes. If you are, you need to edit the patch to add the prefix.