I've my new card ready on hand now.

Out of the box, putting it into the PSP and checking it's information it is indeed MagicGate supported.

Formatting completed.

Rechecking MagicGate, still supported.

Connecting to USB... Connected successfully.

Created new UPDATE folder without issue.

EBOOT.PBP copied successfully, usb disconnected.

Attempting to run 5.03 update with USB cable disconnected and AC power connected to avoid complications...

Update is now running flawlessly. I can therefore assume that the only issue was with the memory stick I originally had, probably defective. Thanks for the help kamen.