I am experienced in Python so trying to help you. Please note the Anaconda 4.0.0 which is shipped with mkl enabled by default it has above issue. A problem is without a doubt with the Anaconda, as I can show it to you with a very simple python test shown below.
Above issue is with Anaconda which is linked with a mkl but it is not with a libmkl_core.so, So one can say it has the missing symbol and now you can cross check by running:
$ LD_DEBUG=symbols python -c 'import sklearn.linear_model.tests.test_randomized_l1' 2>&1 | grep -i error 2200: /opt/anaconda/lib/python2.7/site-packages/scipy/special/../../../../libmkl_avx.so: error: symbol lookup error: undefined symbol: mkl_dft_fft_fix_twiddle_table_32f (fatal)
If you do not want to uninstall your mkl, because of the performance boost so you can do a workaround just preload libmkl_core.so before the execution as shown below.
$ python -c 'import sklearn.linear_model.tests.test_randomized_l1'
Intel MKL FATAL ERROR: Cannot load libmkl_avx.so or libmkl_def.so.
$ LD_PRELOAD=/opt/anaconda/lib/libmkl_core.so python -c 'import sklearn.linear_model.tests.test_randomized_l1'
Hope my above solution saved your lot of time.