Sure if they did not agree to a sublease. They have a right to determine in good faith if you are or are not a good tenant.
My name is Stephen R. Cohen and have practiced since 1974. I practice in Los Angeles and Orange County, CA. These answers do not create an attorney client relationship. My answers may offend I believe in telling the truth, I use common sense as well as the law. Other state's laws may differ.. There are a lot of really good attorneys on this site, I will do limited appearances which are preparation of court documents it is , less expensive. However generally I believe an attorney is better than none.
In San Francisco, a landlord-tenant relationship is typically governed both by the written lease and any applicable rent control provisions. The San Francisco rent control ordinance sets forth certain limitations and rights with regard to subletting (which I will cut and paste for you below). It sounds as though the lease provides more leeway in permitting a roommate or subtenant than is required by the rent control ordinance. If that is the case, address the landlord regarding the terms of the lease and the "new tenant" language you mention above. It is difficult to interpret a lease without reviewing the full agreement, but it sounds as though the lease may contemplate the addition of a new tenant, and may include language the constitutes an agreement by the landlord to allow a subtenant or roommate to share the rent, so long as notice is given. Here is what the rent control ordinance provides: "...(A) Provided that notwithstanding any lease provision to the contrary, a landlord shall not endeavor to recover possession of a rental unit as a result of subletting of the rental unit by the tenant if the landlord has unreasonably withheld the right to sublet following a written request by the tenant, so long as the tenant continues to reside in the rental unit and the sublet constitutes a one-for-one replacement of the departing tenant(s). If the landlord fails to respond to the tenant in writing within fourteen (14) days of receipt of the tenant's written request, the tenant's request shall be deemed approved by the landlord.
(B) Provided further that where a rental agreement or lease provision limits the number of occupants or limits or prohibits subletting or assignment, a landlord shall not endeavor to recover possession of a rental unit as a result of the addition to the unit of a tenant's child, parent, grandchild, grandparent, brother or sister, or the spouse or domestic partner (as defined in Administrative Code Sections 62.1 through 62.8) of such relatives, or as a result of the addition of the spouse or domestic partner of a tenant, so long as the maximum number of occupants stated in Section 37.9(a)(2)(B)(i) and (ii) is not exceeded, if the landlord has unreasonably refused a written request by the tenant to add such occupant(s) to the unit. If the landlord fails to respond to the tenant in writing within fourteen (14) days of receipt of the tenant's written request, the tenant's request shall be deemed approved by the landlord. A landlord's reasonable refusal of the tenant's written request may not be based on the proposed additional occupant's lack of creditworthiness, if that person will not be legally obligated to pay some or all of the rent to the landlord. A landlord's reasonable refusal of the tenant's written request may be based on, but is not limited to, the ground that the total number of occupants in a unit exceeds (or with the proposed additional occupant(s) would exceed) the lesser of (i) or (ii): (i) Two persons in a studio unit, three persons in a one-bedroom unit, four persons in a two-bedroom unit, six persons in a three-bedroom unit, or eight persons in a four-bedroom unit; or,
(ii) The maximum number permitted in the unit under state law and/or other local codes such as the Building, Fire, Housing and Planning Codes; ... ."
It sounds like your roommate breached a term of the lease by not informing the landlord that you would be moving into the unit within 30 days. A breach of a lease term is grounds for eviction (even in a city with local tenant eviction protections like San Francisco) but ONLY if the breach is a "material" breach. That is to say that the breach cannot be merely technical or minor. If the lease allows your main roommate to have any roommate he or she wants and the landlord's only complaint is that there was not timely disclosure of your tenancy, you can argue that the failure to disclose was not a "material" breach since the landlord was seemingly unharmed by your moving into the unit.
Furthermore, the landlord cannot evict you (and your roommate) for subletting in violation of the lease if the landlord has unreasonably withheld consent to the sublet following a written request by the master tenant as described in section 37.9(a)(2) of the Rent Ordinance.
Depending on your circumstances and assuming your unit is covered by the eviction protections of the Rent Ordinance (generally, a building built prior to 1979), you could temporarily move-out of the unit and stay somewhere else for a couple of weeks. Immediately after your "move-out," have your main roommate request consent to you moving in by serving a SF Rent Board 6.15 notice on the landlord. A 6.15 notice is the procedural mechanism under the Rent Ordinance that allows one roommate to get formal approval of a new roommate. By law, a 6.15 notice must be presented to the landlord PRIOR to a new roommate moving-into the unit. Also by law, upon receipt of the notice, the landlord has 14 days to approve or disapprove -- and again a landlord cannot unreasonably withhold consent to a reasonable replacement roommate. However, if the landlord has a standard application used for all potential new tenants, you can be required to fill-out that application. The landlord has five business days to process a new tenant application.
Generally speaking, attempting to serve a 6.15 notice on your landlord is a little problematic for you if you have already been living in the unit but it might be worth a try. More information and advice is generally available from both the San Francisco Rent Board and The San Francisco Tenants Union. Good luck!
In addition to AVVO's general disclaimer, please note that by this answer does not create any sort of attorney-client relationship. I am not your lawyer and this answer is not an attempt to solicit business. This answer is general in nature and does not consider all specifics of a particular query. No answer should ever be relied on in whole or in part, directly or otherwise regarding any potential legal claim. Someone seeking legal assistance should obtain the representation of an attorney in order to properly protect his or her legal rights. I am only licensed to practice law in California and laws differ between different states and localities.