For reference, by 390X ($369 at my local retailer) is doing a average of 34MH.
The only changes in my run line are -
--cl-local-work 256 --farm-recheck 200

Here are my build notes for Ubuntu 15.10

**Don't bother with a card with less than 2GB of RAM, it won't load the DAG.

sudo apt-get install aptitude
sudo aptitude install openssh-server

sudo apt-get -y update
sudo apt-get -y install language-pack-en-base
sudo dpkg-reconfigure locales
sudo apt-get -y install software-properties-common
wget -O - http://llvm.org/apt/llvm-snapshot.gpg.key | sudo apt-key add -
sudo add-apt-repository "deb http://llvm.org/apt/wily/ llvm-toolchain-wily-3.7 main"
sudo apt-get update && sudo apt-get -y upgrade

sudo apt-get -y install language-pack-en-base build-essential git cmake libboost-all-dev libgmp-dev libleveldb-dev libminiupnpc-dev \
libreadline-dev libncurses5-dev libcurl4-openssl-dev libmicrohttpd-dev libjsoncpp-dev libargtable2-dev \
llvm-3.7-dev libedit-dev mesa-common-dev ocl-icd-libopencl1 opencl-headers libgoogle-perftools-dev qtbase5-dev \
qt5-default qtdeclarative5-dev libqt5webkit5-dev ocl-icd-dev libv8-dev libjsonrpccpp-dev zlib1g-dev curl \
unzip automake autogen yasm autoconf dh-autoreconf pkg-config screen libtool libncurses5-dev libudev-dev \
xserver-xorg-core xserver-xorg-video-ati gdebi gedit execstack dh-modaliases lib32gcc1 dkms

Install AMD Catalyst 15.2 (or latest supported Ubuntu driver)
mkdir displayDriver && cd displayDriver
curl -o AMDdriver-15_2.zip http://www2.ati.com/drivers/linux/radeon-crimson-15.12-15.302-151217a-297685e.zip  --referer http://support.amd.com/en-us/kb-articles/Pages/Catalyst-Linux-Installer-Notes.aspx
unzip AMDdriver-15_2.zip
cd fglr*
chmod a+x *.run
sudo sh *.run
# choose install for Ubuntu (option 2)

I think you have to reboot after the driver install...

Install atitweak, monitor your GPU temps with "atitweak -s"
cd ~
git clone https://github.com/mjmvisser/adl3.git
sudo ln -s `pwd`/adl3/atitweak /usr/bin/atitweak

#cryptopp
mkdir cryptopp && cd cryptopp
wget -O cryptopp562.zip http://downloads.sourceforge.net/project/cryptopp/cryptopp/5.6.2/cryptopp562.zip?r=&ts=1456766520&use_mirror=iweb
unzip cryptopp562.zip && rm cryptopp562.zip
#nano GNUmakefile  // add  "-fPIC" to the CXXFLAGS line so it reads: CXXFLAGS = -DNDEBUG -g -O2 -fPIC

make static dynamic -j2 && sudo make install
cd ~

## build cpp-ethereum

git clone https://github.com/Genoil/cpp-ethereum.git
cd cpp-ethereum

#for the stratum branch
git checkout --track -b origin/stratum

# edit build options in nano cmake/EthCompilerSettings.cmake
# remove -Werror from the first compiler line

rm -rf CMakeCache.txt && cmake -G "Unix Makefiles" -DBUNDLE=miner -DCMAKE_BUILD_TYPE=Release -DEVMJIT=1
make VERBOSE=1 -j2

Run it with:
~/cpp-ethereum/ethminer/ethminer --cl-local-work 256 --farm-recheck 1000 -R ~/ -G -F http://your-farm-address