Ambas construcciones son correctas, «debería ser» puede indicar obligación o suposición, mientras que «debería de ser» solo se usa, actualmente, para indicar suposición.

De todas formas, si bien la norma académica indica que no se use así para evitar ambigüedades, desde el punto de vista gramatical no hay nada que nos permita afirmar que es incorrecto usar la forma «deber de» con el sentido de obligación, y así aparece en textos de los escritores clásicos de la literatura española, recogidos en el Diccionario de construcción y régimen de Rufino José Cuervo.