Your travel agents are incorrect and not up-to-speed on the latest Chinese regulations. China allows for visa-free transit if you are connecting from an inbound international flight to another outbound international flight. Neither the US nor the Malaysian passport is a problem. If transiting Shanghai PVG or SHA airports, you have up to 48 hours between arrival and departure; in all other airports including PEK, you have 24 hours. For the record, HKG is not considered "China" for purposes of travel and immigration--it's treated the same as a separate country. Boo to your travel agents for also not getting this. The airline letting you board should not be a problem as they can tap into the Timatic database where this can be found--although it is possible you will run into a clueless check-in agent that needs some firm persuasion and/or a supervisor. But overall, questions of how to route your tickets should depend on other factors such as pricing, journey time, airline comfort, FFP, mileage earning needs, etc.
The following is of no importance to the travel agent but useful for you should you decide to route through a PRC airport: Upon arrival, you will go through immigration (usually there is a specially-signed desk for "international transfers") and get a transit stamp in your passport. If you have a long-enough connection where it makes sense to do so, you may leave the airport during your layover period. Don't listen to anybody who tells you otherwise, just take it from the China experts here on FT. In fact, many people who transit through Shanghai take advantage of the 48 hour limit to make it a full nearly 2-day stopover with a bit of time to look around. At any rate, there will be another pass through immigration then security to get airside for the outbound flight.
That said, other non-PRC airports are more user-friendly and have better amenities for the transit/connecting passenger: NRT, ICN, HKG, maybe TPE. I'd tend to try to route the connection through an Asian airport that is not too far north, if it's cost effective. I presume you have already tried pricing the most direct option--MCI-LAX + LAX-KUL on Malaysia Airlines?