Recommended approach. I recommend that you use SSL and authenticate the client using their password. Then you won't need any fancy MAC, hash, PBKDF2, etc.
Details. You asked how to authenticate the user. Here is a simple approach. Use SSL sitewide. When the user logs in (entering their password in via a web client), then set a session cookie that remembers the user for the rest of their session. (Make sure to use SSL throughout, and to set the secure flag on all cookies.) If you want, you can set a persistent secure cookie once the user authenticates, so they will never need to enter their password again on this browser.
If you want to access the web service from a dedicated mobile client, the same approach works fine. The web server can send a secure persistent cookie which the app can store permanently in its app-local storage, and can use that cookie to authenticate the client.
Alternatives. If for some reason the above is not possible, there are some fallback alternatives, but I think they are less preferable and more likely to have security problems. Here's one plausible fallback method:
On the first launch of your mobile client app, it prompts the user for their password, connects to the server over SSL, and sends the password over SSL. The server responds with a random 128-bit authentication key (chosen by the server using a crypto-strength PRNG).
The client app stores this auth key permanently in app-local storage. The server remembers the association between this auth key and the user's account permanently.
All future requests from the client app are authenticated using this auth key, as follows: you append a parameter to the end of the URL that holds the HMAC (under the auth key assigned to this client) of the rest of the URL, any POST data, and any other state that the server will taken into account.
As long as all requests are idempotent (e.g., for non-idempotent actions, you make sure to include a unique identifier somewhere in the URL parameters or in the POST data, and the server does replay detection), this should work OK to protect the authenticity and integrity of requests from the client to the server.
However, it has some security limitations. It does not protect confidentiality. It also does not protect other request headers, response data, and all sorts of other stuff. For this reason, it is not as secure as just using SSL. For instance, a site built using this approach likely will not be secure against man-in-the-middle attacks, due to the amount of other stuff that isn't protected by a HMAC, and thus won't be safe to use on an open Wifi network. For this reason, I suggest you just use SSL across the board and simplify your life, rather than trying to invent your own cryptographic request authentication format.
Security against password guessing. You'll note that none of my proposed approaches involve generating the cryptographic key as a function of the user's password. Users typically choose passwords. You should expect this will be especially true on mobile platforms, where entering passwords is a pain. For that reason, cryptographic keys derived from passwords will generally provide weak security and can often be broken by dictionary search. For instance, an eavesdropper who captures any one request will be able to mount a brute-force password search attack to recover the password and thus the crypto key, if the crypto key is derived from the password.
While PBKDF2 is an attempt to mitigate this as best as possible, the fundamental vulnerability remains. For this reason, I believe it is better to avoid using cryptographic keys that are derived from passwords, whereever possible. My solutions above are more robust in the face of weak user passwords, because they do not involve sending a password or anything derived as a function of the password in the clear over any connection.
The third-party design. You mention you hired a third party to come up with a design, and they proposed using something like MD5(secrets + data + more data). This is a bad idea. Don't do it. It has multiple cryptographic flaws. First, MD5(secret + data) is a poor message authentication code; it is susceptible to message extension attacks. Second, combining different kinds of data by concatenation is a bad idea and one of the top-ten most common crypto mistakes; both Amazon and Flickr had high-profile security flaws due to this. Instead, I recommend that you use a proper message authentication code (like HMAC), and that you use proper methods for concatenating the data fields that you want to authenticate, e.g., by including length fields.