There's actually a Catalina island off of the coast of SoCal, so that's the first thing I thought of. Not a negative connotation, for me, and actually makes me lean that way. I'm with other posters in I'd spell the other Katerina.
Catalina is Spanish. Caterina is Italian. Katerina or Ekaterina are Russian. I don't know what the origin of Katarina is but I don't like it as it reminds me of the word catarrh, which means phlegm.
Re: Catalina or Caterina
I much prefer Caterina though I don't like the spelling. Katarina is much better IMO.
The Caterina is too close in look to "catering".
TTC since September 2012
Katarina, definitely.
My furchildren, Dorothy and Johnny