TLDR - "sudo apt-get install openjdk-8-source" fixes it.

EDIT: Should've waited for the whole test, but this one is not so critical: "bc" also needs to be installed for the sh_tests to pass (so one more "apt-get install bc")

Here is the full story (without the "bc" failure):
(utopic)malkia@localhost:~/p/google/bazel$ ./bootstrap_test.sh test

*** bootstrap ***

INFO: Starting clean (this may take a while). Consider using --expunge_async if the clean takes more than several minutes.
ERROR: /home/malkia/p/google/bazel/tools/jdk/BUILD:50:1: error loading package 'external': Could not access /home/malkia/.cache/bazel/_bazel_malkia/25bda5d738c2f595d569ca82f756ade7/.external-repository/local-jdk/src.zip: /usr/lib/jvm/openjdk-8 (No such file or directory) and referenced by '//tools/jdk:jdk'.
ERROR: Loading failed; build aborted.
INFO: Elapsed time: 0.609s
Bootstrap failed
(utopic)malkia@localhost:/p/google/bazel$ ls -l /home/malkia/.cache/bazel/_bazel_malkia/25bda5d738c2f595d569ca82f756ade7/.external-repository/local-jdk/src.zip
lrwxrwxrwx 1 malkia malkia 41 Mar 27 00:36 /home/malkia/.cache/bazel/_bazel_malkia/25bda5d738c2f595d569ca82f756ade7/.external-repository/local-jdk/src.zip -> /usr/lib/jvm/java-8-openjdk-amd64/src.zip
(utopic)malkia@localhost:/p/google/bazel$ ls -l /usr/lib/jvm/java-8-openjdk-amd64/src.zip
lrwxrwxrwx 1 root root 20 Mar 17 19:18 /usr/lib/jvm/java-8-openjdk-amd64/src.zip -> ../openjdk-8/src.zip
(utopic)malkia@localhost:/p/google/bazel$ ls -l /usr/lib/jvm/openjdk-8
ls: cannot access /usr/lib/jvm/openjdk-8: No such file or directory
(utopic)malkia@localhost:/p/google/bazel$ sudo apt-get install openjdk-8-source
[sudo] password for malkia:
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following NEW packages will be installed:
openjdk-8-source
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 46.0 MB of archives.
After this operation, 51.8 MB of additional disk space will be used.
Get:1 http://archive.ubuntu.com/ubuntu/ vivid/universe openjdk-8-source all 8u40-b27-1 [46.0 MB]
Fetched 46.0 MB in 16s (2783 kB/s)
Selecting previously unselected package openjdk-8-source.
(Reading database ... 98820 files and directories currently installed.)
Preparing to unpack .../openjdk-8-source_8u40-b27-1_all.deb ...
Unpacking openjdk-8-source (8u40-b27-1) ...
Setting up openjdk-8-source (8u40-b27-1) ...
(utopic)malkia@localhost:~/p/google/bazel$ ./bootstrap_test.sh test

*** bootstrap ***

INFO: Starting clean (this may take a while). Consider using --expunge_async if the clean takes more than several minutes.
INFO: Found 2 targets...
INFO: From Building src/main/java/libbazel-core.jar (1171 files):
Note: Some input files use or override a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
Note: Some input files use unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
INFO: Elapsed time: 97.663s, Critical Path: 92.35s
==> bootstrap passed

Extracting Bazel installation...
Sending SIGTERM to previous Bazel server (pid=6798)... done.
.............

*** test ***

INFO: Found 69 targets and 19 test targets...
[213 / 323] Still waiting for 54 jobs to complete:
Running (standalone):
action 'CompileProtos src/main/protobuf/libproto_build.jar', 10 s
action 'CompileProtos src/main/protobuf/libproto_bundlemerge.jar', 10 s
action 'CompileProtos src/main/protobuf/libproto_crosstool_config.jar', 10 s
action 'CompileProtos src/main/protobuf/libproto_test_status.jar', 10 s
Scheduling:
action 'CompileProtos src/main/protobuf/libproto_xcodegen.jar', 12 s
action 'CompileProtos src/main/protobuf/libproto_extra_actions_base.jar', 12 s
Executing genrule //examples/gen:genrule, 12 s
Building src/java_tools/buildjar/libjava-langtools-location-lib.jar (1 files), 11 s
Building src/java_tools/buildjar/libjavac-bootclasspath-locations-lib.jar (1 files), 11 s
Extracting interface //third_party:truth, 11 s
Linking src/main/cpp/libmd5.so, 11 s
Building src/main/java/libjava-toolchain-parser.jar (11 files), 11 s
Linking src/main/cpp/libutil.so, 11 s
... 41 more jobs