You should switch the field from a calculation to an auto-enter text field so it can be properly indexed for value lists.
I'm having trouble seeing why that would index any differently from a stored calculation field with a text result.
I'd try re-indexing the field myself.
Thank you both for the reply, I changed the calculation to an auto enter text field but this did not resolve the issue.
Re-indexing the field worked for me, thanks for the help.