Run get_terms like this:
var_dump(get_terms('category',array('hide_empty'=>false)));
And then like this:
var_dump(get_terms('category'));
You should be able to infer what is happening. The first should return the zero based array you expect, with neatly numbered keys. The second does not. The only difference being the hide_empty argument.
If you really must have a zero based array just pass the results though PHP’s array_values:
var_dump(array_values(get_terms('category')));