I have a slightly similar problem.
I Had Artio Joom SEF 3.3.0 installed and an AJAX search module from Yoo Tools.
When I search for something I get the error below , pointing me to joomsef
Fatal error: Call to undefined function: array_diff_key() in /home/sites/lovemypub.co.uk/public_html/components/com_sef/joomsef.php on line 616
I get the same error with the AJAX search module disabled and the Joomla search module in place.
If I disable the Joomsef plugin, The search module works fine, but i do actually want the Joomsef module to work.
I have now upgraded to Joomsef 3.3.3 via the upgrade manager in my admin panel and am using Joomla 1.5.10
It wouldnt be a problem to uninstall and reinstall joomsef at the moment as the site is still under construction.
Could anybody offer any advice? The site is here
www.lovemypub.co.uk