P-C, excellent letter. Regarding ita's point:
Sufficient notice for what? If you signed a lease which means you have to pay until the end of the lease, there's no official definition of "sufficient." In that absence, you should define it in the letter.
How about changing this:
I believe I gave sufficient notice of my situation, and I believe both Deb and I have done our best to secure a tenant for the four months remaining on my lease. I cannot afford to pay rent both here and in my new location, however. I am requesting that I be let out of my lease early, and I am willing to forfeit my security deposit for this privilege. Thank you.
To something like this:
In light of the fact that I gave [state how much time will it be--two months?] notice of my need and reasons for vacating, and because the realtor selected new tenants who were not available to enter a lease when the apartment becomes vacant, and I am requesting that you let me out of the lease, effective [whatever date]. I will, of course, pay my rent through [whenever it is], and am willing to forfeit my security deposit for this privilege. Thank you.