Alright so... after weeks of giving this thought... getting some awesome help and trying lots of different things, I was finally, for sure, able to solve the problem I was having.
You see as a previous MobileMe user when I upgraded to iCloud my phone eliminated MobileMe - as it was supposed to - but when doing so it didn't eliminate it as the default account that new contacts were added to. It's a bit confusing but in the simplest terms, my phone was trying to add contacts to a location within it that did not exist, or at least to a location that the rest of my phone's operating system did not recognize.
Enter the awesome app developer Wim de Nood, creator of Cleanup: Remove Multiple Contacts Fast (link below), who's app had enabled other individuals with a similar but quite different problem resolve their issue.
Wim suggested that I confirm that my phone's default contact list was set to iCloud. This is found under Settings > Mail, Contacts, Calendars > "Contacts Heading" > Default Contacts List. The problem was I didn't have the option to select my "Default Contacts List" the button was literally not there.
Wim then suggested that I install another app that he created called Mail Many (link below) which included a de-bug diagnostic which was designed to email him the info on how your phone's contacts list was setup. Upon sending Wim the diagnostic info, he informed me that the diagnostic indicated that my phone was still storing my contacts in the MobileMe "area" of my phone, an area the operating system didn't recognize. This is indicated by the the number 2 after the Default source ID, as seen here: Default source name: (null). Default source ID: 2
------------------
Diagnostic info
------------------
iOS Version: 5.0.1
iPad: 0
Sources:
Source name: (null). Source ID: 2. Source Size: 1
Source name: Card. Source ID: 4. Source Size: 995
Default source name: (null). Default source ID: 2
Wim then suggested I add an Exchange account to my phone. Settings > Mail, Contacts, Calendars > Add Account. I already had several Gmail accounts syncing with my phone but those clearly weren't allowing me to select the Default Contacts List so I created a throwaway Gmail account and then added it to my phone via the Microsoft Exchange option under Add Account following the instructions found under the heading "Setting Up Google Sync with your iOS device" which can be found here:
http://support.google.com/mobile/bin/answer.py?hl=en&topic=14252&answer=138740
This listed the just added Gmail account under Accounts and under which the option to sync Contacts was included and turned on by default.
Unfortunately when I scrolled down to look for the area to select my Default Contacts list, the option still did not exist.
I was pretty bummed as I felt like I'd cracked the problem... no luck though.
After doing some thinking about it though, I went to Phone (app) > Contacts > Groups and saw that my Gmail Exchange listing had no contacts in it, as it was an account created solely for the purpose of trying to solve this problem. I then added a Test contact to the Gmail Exchange Group (clicked on the little + sign) and then went back and looked at the options under Settings > Contacts. Low and behold I now had the option to select a Default contact list!
I set set the default to the recently added Gmail Exchange account and added a contact from the Recents list under SMS / iMessages. I then went back and switched the Default setting to iCloud. Added another contact from Recent's and presto! My newly added contacts no longer disappeared!!!!
I ran the Diagnostic option again under the Mail Many app and low and behold now the default source ID was listed as 4 instead of 2 as seen here:
Default source name: Card. Default source ID: 4 - 4 meaning the default account was now iCloud.
------------------
Diagnostic info
------------------
iOS Version: 5.0.1
iPad: 0
Sources:
Source name: (null). Source ID: 2. Source Size: 1
Source name: Card. Source ID: 4. Source Size: 999
Default source name: Card. Default source ID: 4
Problem solved!! And to think those Apple "Genius'" said I'd have to do a fresh install of the iOS... here's to you boys, a bit of diligence and some inside help can go a long way!
Thanks to Wim for hanging in there with me through all my emails, I do appreciate it.
His apps:
Cleanup: http://itunes.apple.com/us/app/cleanup-remove-multiple-contacts/id376235560?mt=8
Mail Many: http://itunes.apple.com/us/app/mail-many/id378068743?mt=8