That's interesting but I'm not sure launch date should be the date that determines when it's fair for you to have a name. FiftyThree's Paper is no doubt the better one (I was at WWDC and applauded them when they won their ADA), but some apps take a very long time to build. While you're building your masterpiece, some bozo could start and finish a lesser app and use your name before you have a chance to do anything about it.
If your apps biggest selling point is that its named after a commonly used noun then I think you have problems. Its a similar concept to idea vs execution. We saw the same thing at the start of the internet revolution with domain squatting.
If they (MiSoft) had filed a trademark application for "Paper" around the same time they reserved the name with Apple, they might have a case. But reserving a name with a retailer – without actually using it, and without anyone (other than Apple) knowing you were planning to use it – would not to my knowledge have any legal effect with regards to usage rights.
