My first job out of uni was for a startup in Melbourne, Australia. After 3 years the place was running out of cash. The company was betting its entire future on this iPhone app that we were developing for them (iPhone 3G era). It was finished in about 3 months and we submitted it to the app store. Apple had taken over 2 months to reject the application and the process to get it approved took almost 6 months. This was a voip app and Apple's reasoning was that it was potentially competing with their own products. By the time it was approved the company was pretty much finished and I'd taken up another job.

As crappy as the whole process can be it is still a million times better than pre-iPhone Nokia. We had to pay thousands of dollars to get a dongle license just to be able to develop for Nokia phones. After you finish you have to pay money and submit it to an "approved" test house so they can run through a bunch of test cases. If your app failed you had to pay again and resubmit.