Why does GPG not decrypt with all subkeys

For OpenPGP keys, it is not as easy as with SSH. The fingerprint is not calculated from the whole Base64-encoded public key, but only on some (binary) parts of it.

For a version 3 OpenPGP key, what you'd have to do is:

1. Parse the OpenPGP public key packet
2. For RSA, extract modulus and exponent
3. Concatenate their binary values
4. Calculate the hashsum

For step 1 and 2, you can rely the tool pgpdump, which can parse and output the numbers using the -i flag.

For version 4 keys, it even gets more complicated.

If you want to calculate the hashsum for educational purposes, I'd recommend extending pgpdump instead and use all the available parser code, so you can directly work on the extracted information. I'm pretty sure handling the binary information will be easier than with pure shell code, either.

UPDATE: You used the wrong integers. Use the ones in lines RSA n and RSA e instead. Putting everything together in a few lines using standard tools:

pgpdump -i publickey.pub | \
grep -E '(RSA n|RSA e)' | \
cut -d'-' -f2 | \
tr -d "\n " | \
perl -e 'print pack "H*", <STDIN>' | \
md5sum

pgpdump -i dumps the key's MPIs, which we grep out, cut off eeverything we don't need, translate away all the whitespace, convert to binary using perl and finally calculate the md5sum.

Running on the key your provided:

$ pgpdump -i publickey.pub | \
> grep -E '(RSA n|RSA e)' | \
> cut -d'-' -f2 | \
> tr -d "\n " | \
> perl -e 'print pack "H*", <STDIN>' | \
> md5sum
00c9218ed1ab7037dd67a23a0a6f8da5  -

Seems pretty much to be what we're looking for.

For the sake of completeness, the same for version 4 keys, where you need another toolchain. We need the full public key packet. To decompose an OpenPGP message, gpgsplit comes in handy. Afterwards, you can immediately calculate the sha1sum of the file:

gpgsplit publickey.pub; sha1sum *.public_key

For example, running on my own key:

$ gpgsplit publickey.pub; sha1sum *.public_key
0d69e11f12bdba077b3726ab4e1f799aa4ff2279  000001-006.public_key

About Primary Keys and Subkeys

The master key (like the private key) was used to sign data that only the subkey (the public key) could decrypt, but the subkey (the public key) could only encrypt data, which could then only be decrypted by the master key (the private key). Am I correct in this assumption, or are they 2 separate key-pairs altogether?

You haven't got the concepts of public/private key (also called assymetric) cryptography quite right. Each set of public and private keys is split, you publish the public key so others can use it and keep the private key private. Signatures issued by the private key can be verified through the public key, messsages encrypted using the public key can be decrypted with the private key. There is no immediate relationship between primary key and subkey pairs in OpenPGP, these are completely different key pairs.

Is it just GnuPG that uses this method, where a subkey is created automatically for encryption, or is this mandated by the OpenPGP protocol?

The default setup in GnuPG is you have a primary key pair used for certification and signatures, while the encryption subkey is used for encryption only. Using RSA, you could also generate primary keys supporting all those operations (and with GnuPG and the --expert flag, you can!). This is mostly because of other algorithms like DSA and Elgamal, which only support one of the operations (DSA is for signing only, Elgamal for encryption) where you need to have different keys.

There is also some advantage in having different keys for different usages: consider a flaw is found that allows to calculate a private key from signatures under certain conditions. While your signing key would be targeted, the encryption subkey is another one and not targeted by this attack. Some people even consider restricting the primary key to certification only and adding two subkey pairs is best practice, one for signing, one for encryption.

Binding Signatures

If they are 2 separate key-pairs, what mathematically binds the subkey to the master key?

In OpenPGP, a special kind of binding signature is issued when a subkey is created. Subkeys capable of signing can also issue such a binding signature on the primary key. Those special signature are defined in RFC 4880, OpenPGP, 5.2.1. Signature Types:

   0x18: Subkey Binding Signature
       This signature is a statement by the top-level signing key that
       indicates that it owns the subkey.  This signature is calculated
       directly on the primary key and subkey, and not on any User ID or
       other packets.  A signature that binds a signing subkey MUST have
       an Embedded Signature subpacket in this binding signature that
       contains a 0x19 signature made by the signing subkey on the
       primary key and subkey.

   0x19: Primary Key Binding Signature
       This signature is a statement by a signing subkey, indicating
       that it is owned by the primary key and subkey.  This signature
       is calculated the same way as a 0x18 signature: directly on the
       primary key and subkey, and not on any User ID or other packets.

Addressing Subkeys in GnuPG

When I upload a key to a keyserver, which key is uploaded, my master key or the subkey? Or both?

When I use the --export function, which OpenPGP key is exported when I specify my UID?

Usually, in GnuPG key IDs and UIDs are always resolved to the primary key. All export operations (and uploading to a keyserver is also considered an export) also export the subkeys, user IDs and certifications on your key. Similar things exist for other operations like signing and encrypting. If you really want to denote a subkey for operations, you have to add ! behind the subkey (eg. gpg --recipient 0xDEADBEEF! --encrypt).