I have experienced such situation in a company attempting to make the agile move.
The agile way is fairly simple and straight forward and actually removed (or should have) a lot process heaviness. But it was difficult and to my knowledge they are still struggling with it.
The biggest hurdle was that people lacked understanding of what going agile means. I think the change is similar when going from a procedural language to object oriented programming. Writing classes and doing inheritance does not mean you are doing OOP, in much the same way doing daily stand-up meeting and shortening the iterations does not mean you are agile.
Agile is about getting feedback on your work as soon as possible such that this feed back can be integrated back in the product AS IT IS BEING CREATED.
Waterfall is about attempting to get everything down before starting and not look back until it is done. Only a finished product warrants review and starts a new iteration.
I guess you could say in some ways the difference between agile and waterfall is akin to the difference between guided missiles and ballistic missiles. One fires right away and continuously adjust the trajectory in-flight while the other aims very carefully before firing a dead weight.
What ended up being done as "agile" was that they split the waterfall process in smaller iterations. But they still worked all before it started. Though this enabled some parallelism the work was still divided in the basic waterfall view, first get requirements, then design, then code, then test and ship, each part by a different team each team working independently. They applied the agile in apparence but their hearts and minds remained firmly in the waterfall way. When told it was not agile enough they just dropped the design part and created a mess !
It may take some time for your team to truly grok what agile is all about. Not all believe in the agile way and it is very hard to get a non believer to abide to it. Perhaps some external fresh set of eyes and ears can get your team off the ground faster and more efficiently.
I should point out that the process in place at the company, modelled after waterfall, was broken before they decided to move to a more Agile way. They thought that this new thing called agile would solve their problems but they never really analysed what their problem was to begin with. Thus they went from bad to worst.
Also, judging from the comment threads I guess my over simplification of both description deserves some clearing up.
In their own ideals both process would attempt to seek feedback from customers, ideally from the actual users of the system being created. For Waterfall this means that each successive stage should have an open dialogue with the stage before to understand and perhaps fix problems before it reaches them. However the cost of finding a problem increases dramatically as the product nears completion especially so if the problem comes from a few stages back. This implies rigorous checking akin to what a carpenter mean by saying "measure 5 times, cut only once". Waterfall is not inherently broken and has worked very well and continues so in cases where the product, once delivered, is not meant to be changed easily. Getting feedback from customer from a large document describing the engineer's understanding of their need is not easy, yet many company will ask customer to commit to a set of highly technical documents they are often not equipped to understand.
Agile embraces the dynamic nature of human nature and how easily Software can follow. The goal of Agile is to translate the requirements in a form the customer will more easily relate to and as such gain more reliable feedback, I believe this was the essence of the Agile Manifesto. It was not meant as a proletarian revolution of software engineers over the establishment, though it is sometimes, unfortunately so, wielded as a hammer meant to destroy all that do not agree. Most agile techniques will hinge on the fact that software should be easily modifiable given a competent team to do so, that the most difficult part is to make sure the project is on track to satisfy an actual existing need as opposed to the perception of this need by an analyst. This requires a deep change in philosophy and does not integrate well with the present corporate structure. Projects must gain financing, for this financing projects must be evaluated very precisely before it ever gets started. This structure tends to favour a waterfall mindset, where once a contract signed it is often worded in a way where the team is bound to the approved documents and must follow a pre-set plan rather than pursue the need that originated the project. A software company will truly embrace Agile when all it's structure will embrace the agile mindset starting with how the work is billed to customers, how the projects are framed legally and contractually etc. At this point my experience is skim and going further would be purely speculative for me but it is certainly something I would be very interested in learning more about.