I might as well answer my own question in case other people run into this.
MIFARE Ultralight tags still begin with a TLV record, not just the NDEF message. The hierarchy is basically TLV->NDEF Message -> NDEF Record. The TLV for NDEF memory consists of 0x03, a 1-byte length field, and then the "payload" consisting of the actual NDEF Message.