Your logical data model can have many-to-many relationships, but they usually gets resolved with an associative table when you create the physical model.

BTW, I tried using Visio to model a database with > 150 tables, and Visio became so slow that it was unusable. If your company will pay for it, ask them to get ErWin or ER/Studio instead. They are both Sooo much easier to use... and they support many-to-many relationships in your logical model!