This was an issue entirely with Visual Studio on my local machine, not TFS.
Apparently when you edit a build definition, Team Explorer 2010 assumes you're doing it for your currently open solution. I still do not know why it could not find the assembly when it was clearly in my bin\Debug directory, but there you go.
The solution was a simple closing and re-opening Visual Studio. I was then able to edit and save the definition with the new parameter and promote to production appropriately.