If anybody ever needs to communicate with a Bluetooth device from a Windows Store or Windows Phone 8.1 app, you have to manually add the following to your package.appxmanifest file (it cannot be added through any UI):

<m2:DeviceCapability Name="bluetooth.rfcomm">
    <m2:Device Id="any">
        <m2:Function Type="name:serialPort" />
    </m2:Device>
</m2:DeviceCapability>

Don't ask how long that took to figure out =)

UPDATE: I finally found the documentation on MSDN for this and it describes the valid values for the various attributes.