Recommendation letter for application to CS graduate program from professors in math?
When applying to graduate school (either PhD or Masters level), it helps to have letters from any past research supervisors or graduate programs. The fact that your advisor at Dept A refused to write you a letter means that you probably do not want that letter. Letters from people who only know you from class or teaching are not as useful as research letters, but they can still be helpful.