Is Bluetooth responsible for my Ubuntu 16.04 much slower startup?

Solution 1:

The problem is not necessarily related to the Bluetooth. Something slow is happening during those two dmesg rows.

I had the same problem after a fresh install to a new SSD drive. It turned out that during the install process Ubuntu found the older HDD's swap partition and registered that in /etc/fstab. After I have removed the older HDD the swap partition was naturally not available and Ubuntu was waiting there for more than a minute without any dmesg row to appear. When I deleted the HDD's swap partition from /etc/fstab the boot became less than 10 seconds.

You may have the same cause or some hardware- but non necessarily Bluetooth-related problem.