Charlie,
I remember someone at DevCon stating that they had a total of 15 connections to MSDE before it started to crawl. It should be able to handle two.
If you call it from two different connections in the QA, do you have the same problem?
On a side note, your stored procedure is not very multi-user friendly. It's possible for multiple users to get the same key. You need to have SQL Server lock the row while you're updating it. Try this:
CREATE procedure spGetKey
@retKey int = null output
as
declare @lnKey int
update Keys set @lnKey = thekey, theKey = thekey + 1
set @retKey = @lnKey
-Mike