I guess you've already solved the problem, but in case someone else comes across this thread, I recently had the very same issue and the solution was quite quick and simple all in all.
After installing Debian in a new partition, booting Ubuntu took too long compared to before.
So, I pressed E key on GRUB, removed the "quiet splash" option and pressed F10 key to resume, which let me see all the verbose going on during the boot process.
Indeed, it stuck at:
* a start job is running for dev-disk-by x2duuid ... [xx seconds/ 1m 30s]
The unknown UUID referred to the swap partition I had within the Ubuntu partition.
Debian had taken it as its own swap and assigned to it a brand new UUID in its /etc/fstab
configuration file.
I checked this by starting on Debian and verifying the UUID not found by Ubuntu was the one that timed out in 1m 30s.
Back to Ubuntu as superuser I commented out the original UUID line for the swap partition and inserted the same line with the new UUID set by Debian, and that was it.
Now it boots quick and mounts the same swap in both Linuxes.
Hope it helps someone.