I make sure to eject the external HD on my desktop before doing so physically, but I always get the "not ejected properly" nag in my Notifications area. using a WD My Passport for Mac which I bought a few days ago.
Curious, is the said drive used for TimeMachine, or merely storage data?
If the latter, try quitting the app that you're using to access the data on the drive, and then eject it.
Are you waiting until the drive's icon disappears? Sometimes the eject process takes a while to complete as there could be cached data that still needs to be written to the drive.