[AC-1388] CustomObject regex query stopped working with Hebrew

My mobile app (android and iphone) has CustomObject regex query that has been working perfectly for several months. We've recently found that it has a bug when used with Hebrew characters. It seems like something has been changed in the cloud service and this is why it stopped supporting Hebrew. Just to clarify, the production version worked fine until something changed several days ago, that didn't involved any code changes. My query is:

Cloud.Objects.query({
        classname: 'custom1',
        page: page_num,
        per_page: RESULTS_PER_PAGE,
        where: {
            name: {'$regex': '^'+ n}
        });

Where 'n' - is a variable of a Hebrew string. The ACS request is:

ACS Request: { url: "objects/custom1/query.json", verb: "GET", data: {"page":1,"per_page":10,"where":{"name":{"$regex":"^ט"}}} })

(In the regex is an example of a Hebrew character) The error I receive is:

400: Error: This regex query is not supported, regex expression should start with ^letter or ^digit

This query still works fine with English, but not with Hebrew.