What sci.lang.japan says about "obrigado".

4.1. Is arigatou (arigato) related to Portuguese "obrigado"?

No. Arigatou (ありがとう), the Japanese for "thank you", comes from arigatai (有難い), a conjunction of the verb aru, "to have", with the ending gatai (難い) which means "difficult". The "ou" ending comes from the conjunction of the adjectival arigataku with the polite verb gozaimasu (originally from gozaru).

Other common examples of this type of conjugation include omedetou gozaimasu (congratulations) from medetaku and ohayou gozaimasu (good morning) from hayaku. The word arigatai existed in Japanese long before the Japanese ever encountered Portuguese. It can be found in some of the earliest Japanese literature such as the manyoushuu.

(source)

So, that answers that. I still don't see why the adjective would go -ku before "gozaimasu", but I suppose it must be an old connection with the "-kunai" forms.

早い
早くない
早くありません
早くあります
早くございます
お早うございます

Not sure anyone would say it now, but maybe people said it then. I still don't really get how -ku + gozaimasu = -ou, but hey.

And why do "hayai" and "medetai" get the honorific o when "arigatai" doesn't?

お可笑しょうございます。 :-)