Debugging message at the top

Since updating the plugin, all the visitors are shown this message at the top of all the webpages, no matter where they are based

Notice: is_404 was called incorrectly. Conditional query tags do not work before the query is run. Before then, they always return false. Please see Debugging in WordPress for more information. (This message was added in version 3.1.0.)

What needs to be done to use the plugin as intended without ruining the visitors’ experience?

P.S. I tried deactivating and activating the plugin and IP2Location Redirection is the plugin that causes this issue.