Galaxy S4 Mini no reconocido por Linux en modo Download

Actualmente estoy intentando Rootear mi Samsung Galaxy S4 Mini, así que para instalar CWM, arranco el dispositivo en modo download usando mi portátil Linux Mint 17.2:

$ adb reboot bootloader

Ahora, como estaba previsto, mi teléfono arranca en modo de descarga, sin embargo fastboot no reconoce el dispositivo:

$ sudo fastboot devices
$ sudo fastboot continue
< waiting for device >

Sin embargo, en lsusb el teléfono aparece claramente:

Bus 001 Device 005: ID 04e8:685d Samsung Electronics Co., Ltd GT-I9100 Phone [Galaxy S II] (Download mode)

Como se puede ver arriba, corro fastboot como Root, por lo que ciertamente no es un problema de permisos.

No encuentro la solución en ningún sitio de internet, así que se agradece cualquier ayuda. Si necesita más información, hágamelo saber.

Permíteme que te eche un cable, por si te sirve de ayuda:

Mi PC:

$ dpkg -s android-tools-fastboot
Package: android-tools-fastboot
Status: install ok installed
Priority: extra
Section: devel
Installed-Size: 154
Maintainer: Ubuntu Developers <ubuntu-devel-discuss@lists.ubuntu.com>
Architecture: amd64
Source: android-tools
Version: 4.2.2+git20130218-3ubuntu23
Depends: libc6 (>= 2.14), libselinux1 (>= 2.0.65), zlib1g (>= 1:1.2.3.4)
Conffiles:
 /etc/bash_completion.d/fastboot df71a6a847b1d7c6499ad718502b651f
Description: Android Fastboot protocol CLI tool
 Fastboot is a diagnostic protocol primarily used to update the flash
 filesystem of Android devices over USB.
 .
 This package provides the fastboot command-line tool.
Homepage: http://developer.android.com/guide/developing/tools/adb.html
Original-Maintainer: Laszlo Boszormenyi (GCS) <gcs@debian.hu>

$ uname -a
Linux dracarys 3.16.0-38-generic #52~14.04.1-Ubuntu SMP Fri May 8 09:43:57 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

Mi teléfono:

Samsung Galaxy S4 Mini GT-I9195
Android 4.4.2
Linux version: 3.4.0-3173303