Li-Ion battery over discharge protection
First, yes, the battery is considered depleted when it reaches 2.75V.  However, this means something different that what you stated.

When a battery manufacturer talks about "C", this refers to the nominal battery capacity.  The capacity is measured in Ah (or mAh), but the units of C are simply A (or mA).  In the case of your battery, C = 4500 mA.

This is usually used when talking about charging/discharging rates.  "Discharging at 0.2C" means "Discharging at a rate of 0.2C"  This is 0.2 x 4500mA = 900mA.  If you discharge your battery at a rate of 900mA, you will get a total of 4500mAh of power before the battery reaches 2.75V.

Why is it so convoluted? Because batteries will supply different amounts of total power at different discharge rates! You could restate the earlier sentence as "they have characterized the battery's capacity at a discharge rate of 900mA, and have determined that the full capacity is 4500mAh."

Take your battery, for example.  If you attach it to a load which draws 900mA, it will provide 4500mAh before reaching 2.75V.  Doing the math: 4500mAh / 900mA = 5 hours of capacity.

Now, imagine that your load is 1200mA.  You would expect that the battery would supply power for 4500mAh / 1200mA = 3.75 hours.  However, you'll find that it doesn't actually last that long.  The battery's capacity actually decreases with a higher load.

If you wanted to know the exact numbers at different discharge rates, you'd have to get data from the manufacturer.

By the way, this value C is also commonly used for charging.  Often, a battery is rated to be charged at a maximum of, say, 0.5C.  This is the case for your battery.  So, when setting your charging current, 4500mA x 0.5 = 2250mA.  You won't want to exceed this :)