Hi Catherine,
I would not heed this advice:
"I have also heard that if you have enough citations that give your business' address some credit and show that it's not spam, you may not have an issue."
It's important to understand that no matter how many citations you get, you are at risk of their 'power' being split between you and any other business sharing the address, and simply confusing the bots further. It might be helpful to visualize being a bot here. If you see 50 references around the web to Jane's Hair Salon, 23 for Jenny's Yoga and 72 for Bill's Martial arts all stating that they are located at 123 Main street, who do you believe?
Therein lies the problem and it's not going to be a winning situation for any of the businesses mixed up in this.
Google has never handled the concept of shared addresses well. Unfortunately, in the real world, people do share addresses, but Google's system is not designed to cope with that, so either one abstains from participation in Google's local products, or finds a way to comply with them.
You mention getting a whole new address. Do you mean the client would move to a new building? That might be an option, but it's an awfully extreme one to go to (having to move your whole business). So the client getting a unique suite number is likely what he/she should do, but yes, you may encounter some fallout when you change the address. This could be minimal or severe. And, yes, they definitely need to be using their local area code phone number on any listing of the business, as well as in crawlable text in the NAP on their website.
I really sympathize with local business owners who are trying to understand Google's non-intuitive system. It's really easy to violate their rules and make mistakes. This is why it's critical to educate yourself as much as you possibly can about this constantly-changing system. And, if you are an SEO selling services and you are really new at Local SEO, I would suggest you advise your client to hire a Local SEO who can bring specialized knowledge on board. It's just too easy to create bad outcomes for the client if Local isn't your area of specialization...and it's even easy to end up with crazy results if you eat, breathe and live Local every day :)!
Your client is in a very bad situation. It may take some months of one-on-one care to get them out of this mess. Set their expectations correctly about this so that they understand the process is going to involve time and money.
Hope this helps!