To get Cortana working you need to (non US)...
1. go to settings then select language (if you have English US make sure it is listed at the top of the list, you need to long press it and choose move up if it is at the bottom, if you only have one language then you don't need to bother moving it, if you don;t have English US then select add languages and choose English US).. you may need to delete the English US and add it again selecting add languages you will be asked if you want to install the language just say install or ok, also it should look something like this
English (United States)
Phone Language: enabled
Regional format: enabled
Speech: enabled
Keyboard: english
2. go to settings and then select region and change country/region to United States and regional format to United States
3. go to settings and then select speech and then select speech language and change to English United States
then restart the phone and Cortana should be working great with the search button