With the second option being the issue, I can think of two possibilities:
1) The plugin version number was not updated properly when the zip file was created. In other words, the plugin is updating just fine, but the plugin in the zip file still has the old version number.
2) There is some type of new compatibility issue with your site and the Easy Theme and Plugin Upgrades plugin. I say new issue since you indicate that it was working before.
I’ve seen #1 many times before. It’s a simple thing to accidentally forget to update the version number before shipping out a plugin update.
The least-technical way to test for #1 is to manually update the plugin (use FTP to remove the old plugin directory and install the plugin zip file as normal). If the version stays the same after updating, the plugin zip file is the issue and you need to contact the plugin developer to ask for a new zip file that has the proper version number.
Try manually updating and let me know the results.