Resolved.
After receiving the stupid error message, 'Your device or computer could not be verified. Contact support for assistance.', from the Mac App Store when signing into my account, I did some digging and found that deleting a file named 'NetworkInterfaces.plist' from Macintosh HD/Library/Preferences/SystemConfiguration/ might resolve the issue I was having with the Mac App Store. While I was in there, I sorted the folder by 'Date Modified' and deleted all the ones that had been modified since the onset of the problem that this thread is about. The files that I deleted were...
com.apple.applepushserviced.plist
com.apple.BezelServices.plist
com.apple.loginwindow.plist
com.apple.TimeMachine.plist
com.apple.TimeMachine.plist.lockfile
com.apple.preferences.accounts.plist
com.apple.preferences.accounts.plist.lockfile
com.apple.AppleShareClient.plist
com.apple.AppleShareClient.plist.lockfile
There may have been a few more, but I don't remember.
I also deleted the following files from the 'SystemConfiguration' subfolder:
com.apple.airport.preferences.plist
preferences.plist
NetworkInterfaces.plist
com.apple.PowerManagement.plist
com.apple.network.identification.plist
com.apple.smb.server.plist
You may or may not have all these files, and it may not have been necessary to delete all of these files. I thought about doing it one-by-one, which you may want to do and then report back to us, to possibly narrow it down to a single file. I think the problem file resided in the SystemConfiguration folder, but I could be wrong. You'd think it would be the TimeMachine .plist files, but the Apple rep already had me delete those files once and it didn't work.
Keep in mind, by deleting those system preference files, you may inadvertently make other undesirable changes to your system. I believe deleting .plist files is completely safe because your system restores any of them that are required to exist. However, one of the undesirable changes I experienced after doing this was that my ethernet card was not being recognized. Fortunately, this had happened to me in the past and what has fixed that every time for me is shutting down my computer and then holding Shift+Control+Option+Power Button for 5 seconds. What this does is cut off all power to the system board. When I booted my computer back up, the ethernet card was being recognized, and I was able to do my backup, and it just backed up again on its own, which is what it is supposed to do.
I hope this helps everyone who is dealing with this stupid issue. If not, I took notes from my call with Apple, and some of the other things we did (which obviously didn't work for me) may be of use to you. Just reply to this thread, and I'll give you that additional info.