I started using Spark this morning, and was really hoping that it would become my favorite iOS email client. Unfortunately, I too am unable to connect to my company's Exchange server. When I attempt to add the account and enter my credentials, I get a message telling me to use the "Back" button and select Google from the Connect to Service screen. I don't know the nature of the problem, but it might help if Spark provided the ability to enter specific domain and server settings, as other email apps do.
I also had difficulty adding my Outlook email account. If I selected "Outlook" from the Connect to Service screen, the account creation failed. If I selected "Exchange," I was able to add the account.
I realize the app is new, and I have no doubt that these issues will be resolved in future updates. Spark has some great features, in my opinion, but it's not practical for me in its current state.