bucko wrote:

How is it grammatically correct? gozaimasu and arimasu are the same words.

While they can fill similar roles some of the time, they are not the same word.
ござる actually has a number of meanings that are not shared with ある. They are also written with different kanji (有る vs 御座る).

ござる is an 音便 of ござ ある (literally, has a seat). However, containing ある isn't the same thing as equalling ある.

I won't comment on the correctness of 申し訳ございません, since I have never directly studied keigo. It is however VERY common in Japan and is the most common way I've heard it said in stores & restaurants (which lends it no credibility, but grammar is descriptive right? ~ございません definitely has become a norm with natives even if it isn't grammatically correct). A quick google search does indicate that many Japanese people view it as incorrect though (but then I see some stuff about 申し訳ありません also being incorrect, so you apparently can't always trust random people on the internet).

Google faceoff:
申し訳ありません:  16,100,000
申し訳ない:          14,400,000
申し訳ございません: 6,820,000

Last edited by Jarvik7 (2009 February 11, 3:57 am)

On another note completely unrelated to 申し訳ございません etc, I remember being outside Tsutaya or some other shop one day in Japan and there was a fierce argument going on outside between the shopkeeper and (I assume) a customer. A police officer was also standing by. The red faced customer was accusing the shop of something (no idea what) and the shopkeeper kept repeating in a loud voice ございません！ございません！ございません！

It was interesting to see that even in such a hostile situation the shopkeeper was using polite language to address the irate customer.