Another way.

[technicalflaw]

In the unlikely case that anyone comes across this, there is another way to do this, by appropriating an existing backup. You'll need an another server that can be used as a destination, but then copy it to your real destination. Note that I haven't verified the stability of this, so caveat emptor etc.

1. Set up the server to contain the intermediate sparse bundle. If you're using Samba, this is a good guide. You can probably use another Mac as a server, or perhaps even the same Mac.
2. Assuming it works, the server will appear in the Time Machine Settings page. Set up an encrypted disk on it. It's sparse, so it won't take up the actual size. This will create the two keys in the System keychain, associating the encryption password with the sparse bundle and your Hardware UUID. If your server has a password (NOT the sparse bundle encryption password), it will first ask you to login to access the disk. Although this password will be saved in your keychain you can delete it later if required.
3. Command-click on the newly added destination, and either Back up to it, or “verify” it. You don’t want it to complete however (although it doesn’t matter), you just want it to progress long enough to create the file.
4. Give it 15 seconds or so, then cancel it. When it settles, check that a sparse bundle file has been created on the intermediate server.
5. Remove the destination from the list (select it, then click the Minus button). The sparse bundle file will remain on your server. Move the sparse bundle to its real destination, and place it in the root-level folder.
6. Manually add the disk containing the file as a Time Machine destination. From the terminal, type sudo tmutil setdestination -ap protocol://user[:pass]@host/share. The -a flag appends the destination instead of replacing all current destinations. The -p flag causes the password for the server to be prompted for (NOT the sparse bundle encryption password). Although you can embed the server password in the URL instead (i.e: -a protocol://user:pass@host/share) you probably shouldn’t. If you’re repurposing an old AirPort Extreme as a server, use afp as the protocol (it may work with smb as well, I don’t know). In the case of AirPort Extreme, where user names aren’t used, use a dummy name (anything will do, for example afp://whatever@Airport-Base-Station-Name.local/share).
7. You should see the destination in the Time Machine settings page. If the countdown to start a backup has begun, stop it by setting the Backup Frequency in the Options… page to Manually (you’ll change it back later)
8. Go back to the Terminal, and enter tmutil destinationinfo and make a note of the ID field value for this new destination.
9. Open the Keychain Access app, and go to the System keychain. Sort by Date Modified, and you should see 3 new entries. Open the one beginning with Time Machine encryption password for…. This is the sparse bundle encryption password, but it is still associated with the old destination. Replace the value in the Account field with the new destination ID you made a note of in the previous step. Any other text fields (Name/Where) seem to not matter.
10. If you no longer need the intermediate server you created to initially host the bundle, you can delete the entry for its password in the System keychain. Its Kind is Time Machine Network Password. There’s no harm in leaving it there however.
11. Cross your fingers, and try to back up to the destination.