I know sometimes you have to redo databinding at various points to get a combobox to recognize a change... but if the DataTable isn't finding all the new rows, thats annoying.
If it's a smallish sample project, you could post it and I could poke around a little. I know it sounds like the database table you're using seems really simple.