your status shouldn't be the problem: http://tinyurl.com/j2bqnnd
See Nr. 4 of the document. The most important part of Nr. 4 seems this to me: "Uncertainties related. Residence status clears the housing office directly to the Immigration Office." So contact your housing office. This is also recommended by the "Bundesamt für Migration und Flüchtlinge": http://tinyurl.com/gqvubcn
. Look for the part "Support from the state".
You can check online whether you comply with the requirements for a WBS in Berlin: http://tinyurl.com/jl2kvtr
I'm no expert but I'm quite astonished that the lady wants a WBS, because your income is above the threshold for social housing.
Hope I could help, Jan