Translation:He spilled his coffee on my new shoes!
I think i explain this in a better way. Think of it as a car. If you buy a brand new car.... Fabrication récent, then the adjective comes after the noun. Didier a une voiture neuve? (Neuf masc) Oui, c'est la dernière Ferrari.
Nouveau ( fem. Nouvelle) George a une nouvelle voiture? Oui, c'est une vieille Mercedes. In this case, the adjective comes before the noun but is not manufactured now.... New acquisition. I hope you can understand it better now.
According to Lawless French you and others are correct to translate this as brand new. See this link which gives a good explanation and examples: https://www.lawlessfrench.com/grammar/neuf-vs-nouveau/
Duo is frustrating in examples like this. There was a whole section a while back where "brand new" was given as the translation, and I seem to remember, in the Tips. However I also looked a bit further in Collins and Reverso and it would appear that if you want to absolutely sure of "brand new" shoes in French then "toute neuve" can be used.