1. project - clean... 해보세요. 그래도 안되면
2. res - drawable-xxx 폴더마다 해상도별 아이콘을 모두 넣었는지 확인하세요.
한군데만 넣으면 다른 해상도에서는 기본아이콘이 나옵니다.

저역시 비슷한 경우가 있었는데 clean 해도 새로고침 다해봐도 아이콘이 안바뀌는 경우가 있더군요.
제 생각엔 캐시 때문인듯 한데 해결 방법으로는 아이콘 파일명을 변경후 AndroidManifast.xml 수정해주시는게 가장 확실합니다.

1. /res/drawable-****/ic_launcher.png -> icon.png 파일명 변경
2. /AndroidManifast.xml 에서 android:icon="@drawable/ic_launcher" 을 수정 android:icon="@drawable/icon"

이클립스에서 워낙 다양한 증상이 발생해서 이런것 때문에 많은 시간을 허비하곤 하죠 ^^;