After some investigation I've found that version of JDK was wrong. I must have installed jdk6 first, then eclipse, then install jdk7 and then installed pydev. My default jdk was 6 (this can be changed, as stated here). When eclipse is fired from jdk6, it will never see pydev. When I run eclipse manually under jdk7, pydev appeared :)
./eclipse -vm /usr/lib/jvm/java-1.7.0-openjdk-i386/bin/java
so make sure you use jdk7 to run eclipse and it should be fine.