N wo arigatou
This type of structure is a very common one in Japanese, where the N(oun) is a direct object of the last word which is a verb. At that point I had to ask "is arigatou a verb?". This led to some interesting conversation of which I can't say I have a complete understanding, but the basic idea is as follows. There used to be a grammar construct which is very rarely used now, but was much more commonly used in the distant past. It is as follows:
V-stem + gatai
Which meant "difficult to do V(erb)." For instance, difficult to eat would be tabegatai, or difficult to sleep would be negatai. Apparently arigatou used to be arigatai. I'm not sure how "difficult to have" (or any other of the several variations in meaning of arimasu) eventually became "thank you" but it kind of made sense when Sensei explained it :) As a side note, the V-stem + gatai grammar construct has been replaced with V-stem + nikui for meaning "difficult to V".