I graduated DLI in Arabic and have had this question posed to me before. I have never used Rosetta Stone, but am suspicious of any language program that does not use live verbal instruction. Hearing the sounds and pronunciation in person is of incredible importance in learning any language.
I have a friend who went to a JC and took a class taught by a former CTI. I would help him with pronunciation and basic conversation. And it sounded like he was learning (not at DLI pace though.) Also, some military bases have language centers. And you are not too terribly far from one that I know could help.
Arabic is not easy, but with a couple of years of instruction, you can become passable at Modern Standard Arabic. The challenge is this: you sound like you are talking Shakespeare to the average Arabic guy. I had a Jordanian friend who said I sounded like a newscaster when I spoke. So, to really understand and be understood, you have to learn dialects. Levantine is for the Syria/Lebanon/Jordan region. Iraqi and Sudanese/Egyptian are other options. I have heard that Saudis speak the closest version to MSA. And the North Africans (Algeria, Morocco, etc.) have their own special twist. But still, I would learn Modern Standard first, it is a good base.