Depending on the range an rs-232 blue-tooth module may also be an option.
It can cost less as zigbee/xbee with... a blue-tooth enabled PC nearby.
If you use a system with interrupted light as detection method it probably should check several times before alerting people. The chance is big the beam will be interrupted when someone dumps some garbage in the bin, which doesn't have to mean it's full yet.
Fortunately a standard Arduino doesn't have to cost much, but it probably is overkill for a project like this. A program to detect and notify the bin's full shouldn't have to be much bigger as 2 KB, communicating doesn't have to take more as 2 pins of the microcontroller and detecting the bin's full could be done with one pin. Smallest Arduinos sold nowadays do have 16KB and 20 IO-pins.
Just starting with an Arduino I wouldn't advice you to program a much smaller microcontroller
(attiny) with the Arduino IDE, but some here already have done so.
Although a project like this doesn't have to use much power, have you considered how it's going to be powered ?