The company I work for is right smack in the middle of this transition. We had something akin to a SaaS model, before SaaS was a "thing". We have 40+ applications, some are desktop thick net .Net clients, others are web based, all of which interact with one another to varying degrees.
Myself and one other person were instrumental in getting the company to a point where it is possible to release in a semi-automated fashion.
Our challenges were similar to what you described - manual work with lots of process wrapped around it to ensure some modicum of governance, which often failed.
Our number one task was getting our software dependencies under control and automating building. We settled on Maven/Hudson/Nexus as the tools of choice. We have a corporate POM that defines many of our baselines that each of the software projects inherit from. We use Hudson both for automated builds as well as one touch deploys (some are even totally automated) to environments, including production (which is not automatic - it requires a human to initiate).
We then spent over a year "cleaning" our old ant build structures and refactoring into Maven. It cost a lot of money. A whole lot. Maven found numerous cyclical dependencies that Ant hid. We defined all the core libraries, versioned and released them, then built the apps outward from there.
Today, 99% of our software builds are totally automated (a few stragglers of low priority products have not yet been converted to Maven). We have total control of our dependency structure. We have a totally automated release process. We have a totally automated deployment process. It took a lot of work, and a lot of money.
The other side of the coin is our runtime environments. This has been a disaster. The teams that run these systems don't have the concepts of automating anything unless it comes shrinkwrapped form a vendor. Plus there was a management structure in place that encouraged manual work with large numbers of employees. Firefighting was highly rewarded (both in cash and prestige). Eventually, the balance has shifted. The management on this side has either been terminated or left when they saw the writing on the wall. Slowly this side is embracing virtualization and a move toward generic environments whose buildouts are automated. There is a long way left to go here. The goal eventually is that we can automatically provision a VM for a product and deploy to it as we need (think a mini-AMI model).
It is hard. Really hard. A lot of companies won't have the energy to go through with this, and it has a lot of ways to go wrong. We have gone through multiple executive level people during this as well as countless mid-level managers. This type of change is not just technical, itis a massive cultural change for a company.
But today, we have a totally automated process for code release all the way from the developers desktop through to production. Depending on the interactions of a piece of software (if it is an edge or core piece), it can moved daily or monthly. The technology itself can allow multiple production moves a day if people so wanted , but for customer reasons we usually limit this to once a day.