I have a 2TB HD attached to my Nvidia Shield used for extra storage, on start up the Shield checks the drive for what seems like ages before the USB Connected message and the Shield is ready to use.
Plug the drive into a Windows PC and run (in a cmd window opened as administrator) chkdsk D: (or whatever letter the drive is). See Using chkdsk to fix a corrupted SD card.
If the drive has bad sectors (or is formatted as NTFS) it can take a long time for Android to scan it.
(Or, if you know Linux, you can install a terminal and busybox and run fsck.)