This definitely needs context to explain why "to many years" = happy birthday.
The meaning of "La mulți ani" is "I wish you live many years".
It's a natural reaction to the inexorable flow of time. This wish is used not only on birthdays but on other anniversaries as well (new year, national day, etc.).
WTF? Why would "la multi-ani andrei" not be accepted? I know that I have seen it with the dash like this - and it's all the same letters.
Ad multos annos!