We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when faulty processors are able to cheat about their original identities, this problem cannot be solved in an a priori bounded number of rounds for $t\geq(n+n\textrm{ mod }3)/3$, where n is the size of the network and t is the number of failures. This result also implies a $t\geq(n+n\textrm{ mod }4)/2$ bound for the case of faulty processors that are not able to falsify their original identities. In addition, we present several Byzantine renaming algorithms based on distinct approaches, each providing a different tradeoff between its running time and the solution quality.