"We are starting a new business."
Translation:Empezamos un nuevo negocio.
Technically, a 'negocio nuevo' is a brand-new business, or a whole new type of business.
Words like 'nuevo' are called meaning-changing adjectives; they have somewhat different connotations, depending on whether they're found before or after the noun.
Here's a website which may help. Scroll down the exceptions to section 4, the list of meaning-changing adjectives.
I'm guessing here, but maybe because 'company' and 'business' aren't always interchangeable. A company can own several different businesses. You can sell a business but maintain ownership of the company that operated it. Although the spirit of the meaning is similar enough that it would definitely get the point across.
I thought establecemos would be better than empezamos, but Duo doesn't like it. I am reporting it.