REST – How to Test a REST Client Against a REST Server with Fixtures?

The point of unit testing isn't to make a magic unit test fairy come and validate your opinion. It's to test the smallest, simplest building blocks of your system, so you're not testing some more extensive functionality and tripped up because something didn't work the way you thought it did. So, can you break this down further? I don't think you can, in which case:

(a) It sounds like a unit test to me, and (b) It doesn't matter whether it's a unit test or not, because it tests what you need testing, which is the point of using unit tests in the first place!

If you feel the procedures are too complex, you may well want to break them themselves into smaller parts (in database procedures or in code), but to do that you would obviously like to have these tests in place first!

A few of my thoughts:

1. Be honest that writing automated tests will take more time. If you're doing unit level TDD (which I would recommend as a starting point if you're going to invest in automated testing), you can expect about 30% extra time needed to code a feature. The key here is explaining that this extra 30% (which is probably higher than 30% in the beginning as your team learns how to write good tests) is an investment built to save costs over time. As least with unit level TDD, the design of your system is loosely coupled and highly cohesive, which makes your system adaptable to change over time. New requirements and unexpected bugs always require changes to your system, so keeping your system in a state where change is easy (from the nice design that comes from TDD) and safe (the set of automated tests that continually verify your system) means that it will cost less money to make those changes.
2. There's lots of debate about the value of Acceptance level and UI level tests given the amount of time it takes to write these tests, how long it takes to run them, and how much maintenance they require. I'd recommend reading this article by James Shore about this.
3. In the world of automated testing, there are good ways and bad ways to do it. If you are pitching automated testing to your management, I would pitch alongside it how you're planning on getting your team trained in writing good tests. The Art of Unit Testing by Roy Osherove, Working Effectively With Legacy Code by Michael Feathers, and The Art of Agile Development by James Shore are all great books that deal with these topics directly or indirectly. You should also look into some sort of coach or formal training as well. It's a big change.
4. In terms of Business Value, #2 and #3 of your points above actually serve your first point, so I'd hammer home on point #1 and talk about how #2 and #3 serve that greater point. Documentation makes your system more understandable, which makes your team work faster. Code Quality makes your system adaptable to change, which makes your team work faster. For business people, it's all about maximizing the flow of value from the time an idea is pitched to the time the idea is delivered as working software.