"Sorry, but we have a very different taste."

Translation: Maaf, tapi kita punya selera yang sangat berbeda.

[XavierLamb9]

"Maaf, tapi kami punya rasa yang berbeda sekali." Is this right?

[WayangOrang]

'selera' is a better word to use in this sentence.

'rasa' can also mean 'taste', or 'feeling'.
rasa manis = sweet taste.
rasa pahit = bitter taste.
rasa dingin = cold feeling.
rasa panas = warm feeling.
rasa sedih = sad feeling.
rasa gembira = happy feeling.