As I keep telling people, the reason you get this error is either:
1) You have an illegal version of the game (bootleg, warez, leaked beta, cracked, etc).
2) The server you're trying to join is running an illegal version of the game.
If you're sure you have a legit version of the game, simply try joining another server. With 500+ JA servers at any one time, you should have no trouble finding a legit one (though you may need to install the patch to see the majority of the servers in the in-game browser!).
PS: Since you say you "bought" the game, I would think it would be legit. However, where did you buy the game?
From some guy online selling questionable (ie: cd-r copied) software? Did it come in a box with manual and jewel case?
Was it super cheap (ie: like $1 or something ridiculous) and perhaps in a different language? (especially if it came from Asia, I might be suspicious of bootlegs)
The fact that the patch "Doesn't work" makes me think it may not be legit (the copy you own).