Nagios sends alert upon "STATE CHANGE" So your requirement "alert when a previously working interface goes up/down" would be met in that case.
As for "status change on interface status" I use check_snmp for many many interfaces on routers/switches/ethernet cards.
The oid to walk and look at all the interfaces is:
Then add the interface index to the end of that to query that particular interface.
For example to qery the E52 interface on a BLN router, you could use oid:
The check command would look like:
command_line $USER1$/check_snmp -H $HOSTADDRESS$ -C $ARG1$ -o $ARG2$ -r $ARG3$ -l $ARG4$ -m $ARG5$