Still looking for answers...
I found out, that the merging of data seems to be the problem. When I create the Network Dataset out of the individual NAVSTREETS regions everything works fine. But I want one big Network Dataset, so I merged the relevant feature classes (Streets, Zlevels, CDMS- and RDMS-tables, ...). Running the tool with these as input, I get the error message (see above). Makes me wonder how I need to treat the turn restriction information, as I believe that's where the trouble starts.