Implementation use `substitute-in-file-name' which substitute environment variables but 
also drop all in front of consecutive directory separators (up to the last 
of those dir. separators). The documentation of `parse-colon-path' dont 
mention about that behaviour.

In unix systems there is no difference between:

I)  /foo//bar/baz
II) /foo/bar/baz

`substitute-in-file-name' would translate I) into:
/bar/baz

In case path to parse contains an environment variable:
FOO=/foo/bar
BAZ=/foo/bar/

A) path="$FOO/bin" ; works (FOO is a directory file name)
B) path="$BAZ/bin" ; fails (FOO is not a directory file name)


Observed same behaviour on this fuction in emacs versions: 19, 20, 21, 22, 
23, 24 and 25.
Attached patch calls `substitute-env-in-file-name' instead of 
`substitute-in-file-name' and it returns same values for 
inputs I) and II) or A) and B).

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
In *scratch* buffer after started session with:
emacs -Q

(let* ((foo "/foo/bar//baz/:/qux/quux/corge//")) ; '//'
   (setenv "FOO" foo)
   (parse-colon-path (getenv "FOO")))
("/baz/" "/")

(let ((foo "/foo/bar/baz/qux/:/quux/corge/:/grault/graply/waldo")) ; `ok'
   (setenv "FOO" foo)
   (parse-colon-path "$FOO"))
("/foo/bar/baz/qux/:/quux/corge/:/grault/graply/waldo/")

(let ((foo "/foo/bar/baz/qux/:/quux/corge/:/grault/graply/waldo/")) ; end with '/' and `parse-colon-path' add another
   (setenv "FOO" foo)
   (parse-colon-path "$FOO"))
("/")

(let ((foo "/foo/bar/baz/qux/:/quux/corge/:/grault/graply/waldo/")) ; `getenv' makes it work somehow
   (setenv "FOO" foo)
   (parse-colon-path (getenv "FOO")))
("/foo/bar/baz/qux/" "/quux/corge/" "/grault/graply/waldo/")

(let ((foo "/foo/bar/baz//qux/:/quux/corge/:/grault/garply/waldo/")) ; `getenv' dont help with '//'
   (setenv "FOO" foo)
   (parse-colon-path (getenv "FOO")))
("/qux/" "/quux/corge/" "/grault/garply/waldo/")

(let ((foo "/foo/bar/baz//qux/:/quux/corge/:/grault/garply/waldo")) ; '//'
   (setenv "FOO" foo)
   (parse-colon-path "$FOO"))
("/qux/:/quux/corge/:/grault/garply/waldo/")

(let* ((foo "/foo/bar")                    ; `ok' foo not end with '/'
        (bar "$FOO/baz/qux/:/quux/corge/"))
   (setenv "FOO" foo)
   (setenv "BAR" bar)
   (parse-colon-path (getenv "BAR")))
("/foo/bar/baz/qux/" "/quux/corge/")

(let* ((foo "/foo/bar/")                   ; foo ends with '/'
 	   (bar "$FOO/baz/qux/:/quux/corge/"))
   (setenv "FOO" foo)
   (setenv "BAR" bar)
   (parse-colon-path (getenv "BAR")))
("/baz/qux/" "/quux/corge/")


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

In GNU Emacs 25.0.50.1 (x86_64-unknown-linux-gnu, GTK+ Version 2.24.23)
  of 2015-09-10
Repository revision: f962c5d6472804f788cdd54631bcc46aab5f59ce
Windowing system distributor 'Scientific Linux', version 11.0.11500000
System Description:	Scientific Linux release 6.7 (Carbon)

Configured using:
  'configure --without-makeinfo --with-gif=no'

Configured features:
XPM JPEG TIFF PNG IMAGEMAGICK SOUND DBUS GCONF NOTIFY LIBSELINUX LIBXML2
FREETYPE XFT ZLIB TOOLKIT_SCROLL_BARS GTK2 X11

Important settings:
   value of $LANG: en_US.utf8
   value of $XMODIFIERS: @im=none
   locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
   tooltip-mode: t
   global-eldoc-mode: t
   electric-indent-mode: t
   mouse-wheel-mode: t
   tool-bar-mode: t
   menu-bar-mode: t
   file-name-shadow-mode: t
   global-font-lock-mode: t
   font-lock-mode: t
   blink-cursor-mode: t
   auto-composition-mode: t
   auto-encryption-mode: t
   auto-compression-mode: t
   line-number-mode: t
   transient-mark-mode: t

Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.
<backtab> is undefined
Quit
completing-read-default: Command attempted to use minibuffer while in minibuffer
user-error: Beginning of history; no preceding item
Quit [2 times]

Load-path shadows:
None found.

Features:
(shadow sort gnus-util mail-extr emacsbug message dired format-spec
rfc822 mml mml-sec mm-decode mm-bodies mm-encode mail-parse rfc2231
mailabbrev gmm-utils mailheader sendmail rfc2047 rfc2045 ietf-drums
mm-util help-fns help-mode easymenu cl-loaddefs pcase cl-lib mail-prsvr
mail-utils time-date mule-util tooltip eldoc electric uniquify
ediff-hook vc-hooks lisp-float-type mwheel x-win term/common-win x-dnd
tool-bar dnd fontset image regexp-opt fringe tabulated-list newcomment
elisp-mode lisp-mode prog-mode register page menu-bar rfn-eshadow timer
select scroll-bar mouse jit-lock font-lock syntax facemenu font-core
frame cl-generic cham georgian utf-8-lang misc-lang vietnamese tibetan
thai tai-viet lao korean japanese eucjp-ms cp51932 hebrew greek romanian
slovak czech european ethiopic indian cyrillic chinese charscript
case-table epa-hook jka-cmpr-hook help simple abbrev minibuffer
cl-preloaded nadvice loaddefs button faces cus-face macroexp files
text-properties overlay sha1 md5 base64 format env code-pages mule
custom widget hashtable-print-readable backquote dbusbind inotify
dynamic-setting system-font-setting font-render-setting move-toolbar gtk
x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 80421 12421)
  (symbols 48 18940 0)
  (miscs 40 39 110)
  (strings 32 12495 3997)
  (string-bytes 1 361986)
  (vectors 16 11158)
  (vector-slots 8 408984 7901)
  (floats 8 131 123)
  (intervals 56 192 0)
  (buffers 976 12)
  (heap 1024 26696 621))