The update was prompted by a text from UAE telecoms firm Etisalat, suggesting it would improve performance.
Instead, the update resulted in crashes or drastically reduced battery life.
Blackberry maker Research in Motion (RIM) said in a statement the update was not authorised, developed, or tested by RIM.
In the statement, RIM told customers that "Etisalat appears to have distributed a telecommunications surveillance application... independent sources have concluded that it is possible that the installed software could then enable unauthorised access to private or confidential information stored on the user's smartphone".
It adds that "independent sources have concluded that the Etisalat update is not designed to improve performance of your BlackBerry Handheld, but rather to send received messages back to a central server".
RIM has now issued its own update allowing users to remove the application.