Immediately, with brutal honesty, and positively.
1. Immediately: Never delay communication. Most people will be less upset about the schedule than the fact that they weren't informed.
2. With Brutal Honesty: Explain exactly what's going on. You may end up with a pleasant surprise. "Oh, can we just have xyz then?" or "How can we reduce the scope?" or " How can we help you make this easier." An informed customer/boss is a resource to be used.
3. Positively: Find a way to deliver something by the deadline. "ABC will be delivered as planned on October 31, but we have run into unexpected issues with Feature xyz, so it may not be fully implemented at that time." sounds a whole lot better than, "We won't hit the October 31 deadline." You may even give them options in terms of features & dates. They may not like it, but once they make a decision, they feel more a part of it and you will have bought some goodwill for a while.