"Debiste haberme(lo) dicho" (you should have told me) es correcto. También podrías decir, "debías haberme(lo) dicho", "deberías haberme(lo) dicho" o "debieras haberme(lo) dicho." Aunque la última opción suena muy formal y es bastante inusual.
En España también es bastante común decir solamente "haberme(lo) dicho," pero sólo al hablar:
-¡Haberme dicho que estabas en la ciudad, te habría visitado!
O- ¿has ido al supermercado? ¡Necesitaba azúcar!
- ¡Habérmelo dicho antes!
De la misma forma, "debí haberte(lo) dicho" (I should have told you) es correcto. O "debía haberte(lo) dicho," "debería haberte(lo) dicho," "debiera haberte(lo) dicho."