The proper translation, as given by http://en.wikipedia.org/wiki/All_your_base_are_belong_to_us :
Japanese:
「君達の基地は、全てＣＡＴＳがいただいた。」
Literal:
"CATS has taken over all of your bases."
Not literal:
"We are now in control of Earth!"

>is the sentence `all your bases belong to us' right?

Yes it's ok, as a literal translation.