I've come across a similar problem - sometimes the cue doesn't work at all until I cue the dvd for a second or third time. I haven't seen it start from the cue after going through the menus, though.
I haven't had a chance to check it out, but it seems that if you don't cue from the very start of a chapter (eg, start playing from 00:00:00.50), the cue may be more likely to work. Your mileage may vary.
thegink