Teaching students how to construct regular expressions (and other "translation" style problems)
This is the stuff of math teachers' nightmares. The problems here, from my experience teaching about grammars1, are two-fold:


You said that syntax is probably not the culprit here. Students may be able to follow a grammar that has been presented to them, but may not be able to generate an appropriate grammar for a given series of test cases.
Students may not be able to generate appropriate test cases from the word problem itself.


The good news is that, by breaking it down into these two steps instead of one, you can actually help to isolate the problem that your students are having.  

If you see your students frequently (as I do), here's a fix-up strategy that you can do in about 30 minutes of class time over three days.  Create a worksheet with a series of word problems, and ask the students, as homework, to generate test cases for these hypothetical machines.  They are not to create the grammars themselves, only create a series of test cases that should be accepted or not accepted.  Emphasize that redundancy is not a goal; you want a minimal set of test cases that could guarantee that some grammar is entirely correct.

The next day, spend about 15 minutes going over two of the problems, round-robin style, at the board.  Ask a student to write a test case for the first problem. Turn to the second student, and ask them to write another test on the board that could potentially uncover new ground.  On to the third student, fourth student, etc., until you are satisfied that you have a good testing set.  Ask if anyone else has any important tests remaining.

Do the same for the second problem, and then discuss the importance (in general) of creating good test sets upon encountering a word problem.  Point out that they will receive word problems on their assessment at the end of the unit, and you expect them to be able to figure out a good set of test cases with which to design a grammar at that time.

Their homework for that second day is to fix up their tests (if they need more work), and to create the appropriate grammars.  I suspect that when you get this homework back on day 3, you'll have much stronger results.

1 - I am using "grammar" as a stand in for "grammars, regexes, FSAs, or whatever type of expression/machine you are trying to get them to create at some particular moment."