Did you install the plugin via the plugin manager?
This does not sound like it's related to the ajax search pro. The menu links are built by wordpress, and it hasn't changed since the initial release.
If you can provide temporary back-end and FTP access, I can take a look at the problem directly.Best,
If you like my products, don't forget to rate them on codecanyon :)