4-5 minutes seems really quick to get that warm. Bleeding the system might be worth a try. As long as the cooling system is full with no bubbles it should take longer than that just to warm to normal, radiator or no. Sounds like you need to replace the radiator anyways, but you'll never know what the problem was if you don't bleed first.
When I drive to my office It's just barely warmed up, 10-15 minutes. The thermostat probably hasn't even opened yet. That's with the temps in the 60's to 80's.
Eric Claussen
La Habra, CA
1993 525i 5 speed