I've never had problems with flashing via ubuntu, except the need to apt-get install ia32-libs on the amd64 version.

The problem is indeed weird, I don't know if it has anything to do, but I never needed to press u when plugging in. The second "Suitable USB device not found" message is normal, but it should be quickly succeeded by the firmware download.

According to the wiki, flashing the emmc when your rootfs is borked may not work, so I would try flashing the rootfs first then the emmc and then rootfs again.

hope that helps.