It is about layers of abstraction.
The core difference is physical-storage vs logical-storage identification. The PART-UUID is for raw physical storage partitions and is a feature of GPT partition tables. A UUID is for identifying logical file systems, it is generated by the creation of the filesystem such as
mkfs.ext4, and then refers to the formatted filesystem not the raw physical partition.
Which one to use depends on your priority, do you want to track physical storage device partitions or do you want to track filesystems?
Use PART-UUID to link to a physical drive partition even if you format it with a new filesystem, this is closest to the old behavior of using /dev/sda4 eg. This does not work for mounting logical volumes if you use LVM2 for example; but PART-UUID can be used within LVM2 for referring to physical storage within a storage pool or physical units in a RAID.
Use UUID to link to a specific filesystem, the filesystem must support it, as such FAT and NTFS which predate the UUID industry standards do not support the common UUID standard.(They do have unique identifiers but formatted different and shorter than a common UUID, Linux will accept them in most cases.) If you bit>bit clone the filesystem to a new physical drive partition the UUID will follow, the PART-UUID will not follow. (You must disable or remove the old copy from the system or there may be a collision.) UUID works with logical volumes and raid volumes,(volume here being a logical filesystem not a physical device) a raid1 btrfs filesystem when scanned with blkid will have unique PART-UUID for each disk partition in the pool but all of them will have the an identical UUID, but then you will also see UUID_SUB (btrfs has its own form of internal logical partitioning called sub-volumes.)
mkswap will generate and assign a UUID to a raw swap partition even though there is no true filesystem involved, but this UUID will change every time you run
mkswap on that partition, while the PART-UUID will stay the same.(This example is easy to test even if you keep swap off.)
If you mix the two ID types in fstab, there is a very small chance that a collision could happen; though it is minor and easy to fix unless it involves / or /boot. Example: If you originally use PART-UUID to mount sda4 on /var/cache/apt and you use a UUID to mount the filesystem you use for /home. Then at some point in the future you clone /home onto sda4 and fail to fully correct fstab, then fstab will now have two totally different mount instructions for the one physical filesystem-partition and will not know if you want it on /home or /var/cache/apt. (Or possibly some other undefined behavior I'm not an init-fstab-mount-systemd expert.) The fix is simply to delete the unwanted line from fstab.
Microsoft calls its special format of UUID a GUID, it serves the same purpose and is included in the industry standards as a UUID variant for backward compatibility.
As for your specific issue I can only think of three possibilties why one ID would work and not the other. It is possible the specific file system in use does not generate a UUID. Secondly the choice of MBR vs GPT for the partition table, MBR does not generate a PART-UUID. The third is just an error like one wrong character. to avoid the third i like to add partitions to the fstab [after making a backup copy] with
sudo blkid /dev/sda4 >> /etc/fstab to get the IDs into the file exactly and then manually edit fstab to format the mount instruction. (
> is over write,
>> is append, be careful)
Do not confuse any of this with a partition-type-GUID which is just a fixed code in a GPT partition table for the exact type of partition and filesystem use. MBR had simple codes but there was not enough room so they were not globally unique codes and had a lot of overlapping uses or covered whole generic categories like "linux filesystems". While a GPT part-type-GUID has more than enough space so that the code for "Solaris /home" is different from "linux /home" or "freeBSD ZFS" or "Plan9 data" etc. But all "Solaris /home" partitions will have the same part-type-GUID.